题解：CF524F And Yet Another Bracket Sequence

· · 题解

题解：CF524F And Yet Another Bracket Sequence

题目大意

给你一个括号序列，两种操作，一个是在任意位置插入一种括号，一种是循环移位，求操作完后合法括号序列的最小字典序。

思路

首先括号序列有个很经典的前缀性质，即在前缀中右括号的个数不大于左括号的个数。

然后对于一操作，无疑就是补上不够的括号，因为要字典序最小，所以左括号放最前面，右括号放最后面一定是最优的。

对于操作二直接复制一遍即可。然后对序列跑一遍 SA，从字典序最小的开始跑，如果它的起点小于 n，长度就合法，然后就是判断长为 n 的这个字串是否是合法括号序列，这个可以用线段树维护，维护的信息就是前缀的右括号与左括号的差。

这里记 cnt 为原串中左括号与右括号的差，判断的时候分讨一下：

  1. 如果 cnt < 0，那么就要在前面添加左括号，又因为是在最前面添加，所以右括号与左括号的差值最下可以是 cnt。
  2. 如果 cnt > 0，那么就要在最后添加右括号，又因为是在最后面添加，所有与前面的无关，所以右括号与左括号的差值最小为 0，不然在前面就已经变成不合法序列了。

具体的见代码

Code

#include <bits/stdc++.h>
using namespace std;
const int N=2e6+5;

int n;
int tax[N],rak[N];
int sa[N];
int tp[N];
int limit;
int pre[N];
int cnt=0;
string s;
struct node{
    int l,r,minn;
}tree[N*4];

namespace Flower{
    inline int read(){
        int x=0,f=1;char c=getchar();
        while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
        while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
        return x*f;
    }

    inline void write(int x){
        if (x<0){putchar('-');x=-x;}
        if (x>9) write(x/10);
        putchar(x%10+'0');
        return ;
    }
}using namespace Flower;

inline void cardinal_sort(){
    for (int i=0;i<=limit;i++)
        tax[i]=0;
    for (int i=1;i<=n;i++)
        tax[rak[i]]++;
    for (int i=1;i<=limit;i++)
        tax[i]+=tax[i-1];
    for (int i=n;i>=1;i--)
        sa[tax[rak[tp[i]]]--]=tp[i];
}

inline void suffix_sort(){
    limit=128;
    for (int i=1;i<=n;i++){
        rak[i]=s[i];
        tp[i]=i;
    }
    cardinal_sort();
    for (int w=1,p=0;p<n;limit=p,w<<=1){
        p=0;
        for (int i=1;i<=w;i++)
            tp[++p]=n-w+i;
        for (int i=1;i<=n;i++)
            if (sa[i]>w)
                tp[++p]=sa[i]-w;
        cardinal_sort();
        swap(tp,rak);
        rak[sa[1]]=p=1;
        for (int i=2;i<=n;i++)
            rak[sa[i]]=(tp[sa[i-1]]==tp[sa[i]]&&tp[sa[i-1]+w]==tp[sa[i]+w])?p:++p;
    }
}

inline void pushup(int now){
    tree[now].minn=min(tree[now<<1].minn,tree[now<<1|1].minn);
}

inline void build(int now,int l,int r){
    tree[now].l=l;
    tree[now].r=r;
    tree[now].minn=0x3f3f3f3f;
    if (l==r){
        tree[now].minn=pre[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(now<<1,l,mid);
    build(now<<1|1,mid+1,r);
    pushup(now);
}

inline int query(int now,int l,int r){
    if (tree[now].l>=l&&tree[now].r<=r)
        return tree[now].minn;
    int res=0x3f3f3f3f;
    int mid=(tree[now].l+tree[now].r)>>1;
    if (l<=mid)
        res=min(res,query(now<<1,l,r));
    if (r>mid)
        res=min(res,query(now<<1|1,l,r));
    return res;
}

int main(){
    cin >>s;
    for (int i=0;i<(int)s.size();i++){
        if (s[i]=='(')
            cnt++;
        else
            cnt--;
    }
    s+=s;
    n=s.size();
    s=' '+s;
    suffix_sort();
    for (int i=1;i<=n;i++)
        pre[i]=pre[i-1]+(s[i]=='('?1:-1);
    //cout <<"check:: "<<endl;
    //for (int i=1;i<=n;i++)
    //    cout <<pre[i]<<" ";
    //cout <<endl;
    build(1,1,n);
    string ans;
    ans.clear();
    int m=n/2;
    for (int i=1;i<=n;i++){
        //cout <<"check:: "<<rak[i]<<endl;
        if (sa[i]>m)
            continue;
        int l=sa[i],r=sa[i]+m-1;
        int minx=query(1,l,r);
        //cout <<"check:: "<<minx<<" "<<pre[l-1]<<endl;
        if ((minx-pre[l-1]<cnt&&cnt<0)||(minx-pre[l-1]<0&&cnt>0))
            continue;
        if (cnt<0){
            int now=l;
            while (cnt)
                ans+='(',cnt++;
            for (int j=1;j<=m;j++)
                ans+=s[now++];
        }
        else{
            int now=l;
            for (int j=1;j<=m;j++)
                ans+=s[now++];
            while (cnt)
                ans+=')',cnt--;
        }
        break;
    }
    cout <<ans<<endl;
    return 0;
}
//Love Flower