【GDOI2018模拟9.17】永远的三日天下

Description

给出一个字符串，求解一个括号序，使得每对匹配的括号所在位置的字符都相等。

使答案字典序最小。

n<=4*1e6

Solution

了上克下行一这得使量力的邪正人鬼

栋栋搬的吼题

首先我们考虑先构造出一组可行解，这个显然可以用单调栈来完成

如果我们把每个时刻单调栈里面的东西想象成一个trie，那么每一组配对x,y都满足x-1和y在trie上所对应的节点相同。

考虑一个贪心，我们当前处理l,r这个区间，我们要给l匹配

那么肯定是匹配最右边一个合法的，即最大的pos满足f[pos]=f[r]并且st[l]=st[pos]

这个可以用一个链表来存，每次把最大的选择之后在链表上往前跳

但注意，我们的这个性质只是一个充分条件，为了满足必要性，我们要从后往前满足这个东西

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=*+;
int n,id[][N],trie[N][],pre[N],cnt;
int stack[N],f[N],last[N],next[N],top;
char st[N],ans[N];
void add(int l,int r) {
    if (l<r) next[l]=last[r],last[r]=l;
}
void solve(int l,int r) {
    if (l>r) return;
    int now=st[l]-'a';
    int pos=id[now][f[r]];
    ans[l]='(';ans[pos]=')';
    add(pos+,r);
    add(l+,pos-);
}
int main() {
    freopen("seija.in","r",stdin);
    freopen("seija.out","w",stdout);
    scanf("%s",st+);n=strlen(st+);
    int x=;
    fo(i,,n) {
        int now=st[i]-'a';
        if (!top||st[stack[top]]!=st[i]) {
            stack[++top]=i;
            if (!trie[x][now]) trie[x][now]=++cnt;
            x=f[i]=trie[x][now];
        } else --top,x=f[i]=f[stack[top]];
        pre[i]=id[now][f[i]];
        id[now][f[i]]=i;
    }
    if (top) {
        puts("-1\n");
        return ;
    }
    add(,n);
    fd(i,n,) {
        while (last[i]) {
            int j=last[i];last[i]=next[j];
            solve(j,i);
        }
        id[st[i]-'a'][f[i]]=pre[i];
    }
    fo(i,,n) putchar(ans[i]);
    return ;
}