這題做得比較復雜。。應該有更好的做法
題目大意：
有一個括號序列，可以對其進行兩種操作：
·????????向里面加一個括號，可以在開頭，在結尾，在兩個括號之間加。
·????????對當前括號序列進行循環移動，即把最后一個括號拿到開頭來。
上述兩種操作可以做任意次，要求添加最少的括號使得原序列變成一個合法括號序列。如果有多種可能，輸出字典序最小的那一個。"("?<?")"。
?
題解：
首先計算左括號和右括號的數量，可以知道，不妨假設左括號的數量大于右括號
那么最少的方案就是在字符串右側補充右括號，使得左括號的數量等于右括號的數量。
但是一個方案是否可行，要使得前面的每個前綴，都滿足條件左括號的數量大于右括號
如果不滿足，就循環移動即可，通過循環移動就一定會找到一個方案。
要輸出字典序最小的方案，就需要后綴數組了
把字符串循環復制一遍，做后綴數組，那么就知道每個方案的排名
找最小且可行的方案輸出即可。
另一種情況是左括號的數量小于右括號，也是同理的。
?
關于如何判斷是否可行，這里是用的平衡樹
寫出每個位置的條件，每移動一次，對所有的條件影響都是相同的，所以用平衡樹維護這些條件即可
#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(")");} }
?
)
