这题做得比较复杂。。应该有更好的做法
题目大意：
有一个括号序列，可以对其进行两种操作：
· 向里面加一个括号，可以在开头，在结尾，在两个括号之间加。
· 对当前括号序列进行循环移动，即把最后一个括号拿到开头来。
上述两种操作可以做任意次，要求添加最少的括号使得原序列变成一个合法括号序列。如果有多种可能，输出字典序最小的那一个。"(" < ")"。
题解：
首先计算左括号和右括号的数量，可以知道，不妨假设左括号的数量大于右括号
那么最少的方案就是在字符串右侧补充右括号，使得左括号的数量等于右括号的数量。
但是一个方案是否可行，要使得前面的每个前缀，都满足条件左括号的数量大于右括号
如果不满足，就循环移动即可，通过循环移动就一定会找到一个方案。
要输出字典序最小的方案，就需要后缀数组了
把字符串循环复制一遍，做后缀数组，那么就知道每个方案的排名
找最小且可行的方案输出即可。
另一种情况是左括号的数量小于右括号，也是同理的。
关于如何判断是否可行，这里是用的平衡树
写出每个位置的条件，每移动一次，对所有的条件影响都是相同的，所以用平衡树维护这些条件即可
#include <iostream> #include <cstring> #include <cstdio> #include <vector> #include <map> #include <set> using namespace std; const int maxn = 2e6 + 1000; int Wa[maxn], Wb[maxn], Wv[maxn], Ws[maxn], sa[maxn]; int Rank[maxn]; int height[maxn]; set<int> S; map<int, int> M; vector<int> V; int a[maxn]; int cmp(int *r, int a, int b, int l) { return r[a]==r[b] && r[a+l]==r[b+l]; } void get_sa(int *r, int *sa, int n, int m) { int i,j,p,*x=Wa,*y=Wb,*t; for(i=0; i<m; i++) Ws[i]=0; for(i=0; i<n; i++) Ws[x[i]=r[i]]++; for(i=1; i<m; i++) Ws[i]+=Ws[i-1]; for(i=n-1; i>=0; i--) sa[--Ws[x[i]]]=i; for(p=1,j=1; p<n; j*=2,m=p) { for(p=0,i=n-j; i<n; i++) y[p++]=i; for(i=0; i<n; i++) if(sa[i]>=j) y[p++]=sa[i]-j; for(i=0; i<n; i++) Wv[i]=x[y[i]]; for(i=0; i<m; i++) Ws[i]=0; for(i=0; i<n; i++) Ws[Wv[i]]++; for(i=1; i<m; i++) Ws[i]+=Ws[i-1]; for(i=n-1; i>=0; i--) sa[--Ws[Wv[i]]]=y[i]; for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1; i<n; i++) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++; } } void get_height(int *r, int *sa, int n) { int i, j, k=0; for(i=1; i<=n; i++) Rank[sa[i]]=i; for(i=0; i<n; height[Rank[i++]]=k) for(k?k--:0,j=sa[Rank[i]-1]; r[i+k]==r[j+k]; k++); } void Hinsert(int x){ if(M[x] == 0) S.insert(x); M[x]++; } void Herase(int x){ if(M[x] == 1) S.erase(x); M[x]--; } char str[maxn]; int tr, tl; int main() { cin>>str; int n = strlen(str), nl = 0, nr = 0; for(int i = 0; i < n; i++){ if(str[i] == '(') nl++, str[i] = 1; else nr++, str[i] = 2; } if(nl < nr){ tl = 0; for(int i = n-1; i >= 0; i--){ if(str[i] == 1) tl++; a[i] = 2*tl-(n-i); Hinsert(-a[i]); } tl = 0; for(int i = n-1; i >= 0; i--){ if(-(*S.begin()) <= -(n-i-1)+2*tl) V.push_back(i); Herase(-a[i]); if(str[i] == 1) tl++; Hinsert(-(2*nl-n-(n-i)+2*tl)); } int N = 2*n-1; for(int i = 0; i < n; i++) a[i] = str[i]; for(int i = n; i < N; i++) a[i] = str[i-n]; get_sa(a, sa, N+1, 4); for(int i = 1; i <= N; i++) Rank[sa[i]] = i; int maxr = N+100, Kr = 0; for(auto i : V){ if(i+1 >= N) break; if(Rank[i+1] < maxr){ maxr = Rank[i+1]; Kr = i+1; } } a[N] = a[N-n]; for(int i = 0; i < nr-nl; i++) printf("("); for(int i = Kr; i < Kr+n; i++) printf("%c", a[i] == 2 ? ')' : '('); } else { tr = 0; for(int i = 0; i < n; i++){ if(str[i] == 2) tr++; a[i] = 2*tr-i-1; Hinsert(-a[i]); } tr = 0; for(int i = 0; i < n; i++){ if(-(*S.begin()) <= -i+2*tr) V.push_back(i); Herase(-a[i]); if(str[i] == 2) tr++; Hinsert(-(2*nr-n-i-1+2*tr)); } int N = 2*n-1; for(int i = 0; i < n; i++) a[i] = str[i]; for(int i = n; i < N; i++) a[i] = str[i-n]; get_sa(a, sa, N+1, 4); for(int i = 1; i <= N; i++) Rank[sa[i]] = i; int maxr = N+100, Kr = 0; for(auto i : V){ if(Rank[i] < maxr){ maxr = Rank[i]; Kr = i; } } for(int i = Kr; i < Kr+n; i++) printf("%c", a[i] == 2 ? ')' : '('); for(int i = 0; i < nl-nr; i++) printf(")"); } }