题目链接
算法：后缀数组+ST表+贪心
各路题解都没怎么看懂，只会常数巨大的后缀数组+ST表，最大点用时 \(4s\), 刚好可以过。。。
确定合法序列长度首先一个括号序列是合法的必须满足以下两个条件：
(的数量和)的数量相等。
序列任意前缀中，)的数量都小于等于(的数量；或者序列任意后缀中，(的数量都小于等于)的数量（在满足条件1的情况下两种说法等价）。
这两个条件共同构成了检验括号序列合法的充要条件。
所以题目中要求的合法序列最小值，其实就是让两个括号数目相等时的总长，让少的那种括号补上就可以了。
让字典序最小现在考虑如何让字典序最小。
1. 括号放置（贪心）不妨设当前)比(少，数量分别为 \(cnt_1,cnt_2\)，为了让序列长度最小，我们只能在序列中补上 \(cnt_2-cnt_1\) 个)。为了让字典序最小，我们把)放在序列末尾，这样做可以在要补全序列满足上述条件 \(2\) 的情况下，最后得到的序列是合法的，而且字典序是最小的。但是当要补全的序列不满足条件 \(2\) 时，不管你怎么加)都不能满足条件 \(2\) 了，所以如果能加)一定是加在末尾的（贪心）。
同理在(比)少时，我们在序列前面补全(，满足字典序最小。这样可以发现，要补全序列和补全括号的部分是完全独立的，所以只要使要补全的序列字典序最小，且满足条件 \(2\), 这道题就解决了。
2. 字典序排列（后缀数组）因为括号字符串 \(S\) 可以循环，这里一般的套路是复制一次原串到末尾，形成循环串。这里要让长度为 \(|S|\) 的字符串进行排序，我们使用后缀数组完成后缀排序。我们只需考虑长度大于等于 \(|S|\) 的串（因为这些串要么前 \(|S|\) 个字符相等，这样取哪个都是等价的；要么不等，那么排序就相当于长度 \(|S|\) 的字符串进行排序）。
剩下问题就是判断这个长度为 \(|S|\) 的区间，是否满足条件 \(2\) 。
3.判断条件2（ST表）这里有个判断括号序列合法的套路，就是把(映射为 \(1\)，)映射为 \(-1\)，得到前缀和 \(lr\_cnt\) 与后缀和 \(rl\_cnt\)。分情况讨论：
\(lr\_cnt_{|S|}=0\) ，满足条件 \(1\) ，因为不用补全括号，所以不用考虑了。
\(lr\_cnt_{|S|}>0\) ，(数目多于)，需要在序列末尾补上)。要使某个区间 \([l,r]\) 满足条件 \(2\) ，就要使 \([l,r]\) 的任意前缀中，)的数量都小于等于(的数量，即对于 \(\forall x,l\le x\le r\) 都有 \([l,x]\) 中(的数目减)的数目大于等于 \(0\) 。因为我们已经求出了前缀和，所以我们可以 \(\mathcal O(1)\) 判断是否满足上述要求：取这个区间上前缀和最小的值，减去 \(lr\_cnt_{l-1}\) ，如果仍大于等于 \(0\) ，说明该区间确实满足上述要求（因为如果这个值都不小于 \(0\) 了，区间其他值肯定也不小于 \(0\)）。求区间最小值，预处理ST表即可。
\(lr\_cnt_{|S|}<0\) ，同理要在序列前端补上(。上面是求前缀和区间最小值，这里就是求后缀和区间最大值了。所以在ST表得分情况处理。
\(Code:\) #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e6+5; char s[N]; int tp[N],rak[N],sa[N],tax[N],sl,m,lr_cnt[N],lg[N],f[N][22],rl_cnt[N]; void radixSort(){ for(int i = 1;i <= m;i++) tax[i] = 0; for(int i = 1;i <= sl; i++) tax[rak[i]]++; for(int i = 1;i <= m;i++) tax[i] += tax[i-1]; for(int i = sl; i ; i--) sa[tax[rak[tp[i]]]--] = tp[i]; } void build_sa(){ m = 125; for(int i = 1; i <= sl; i++) rak[i] = s[i], tp[i] = i; radixSort(); for(int p = 0,w = 1; p < sl; w <<= 1, m = p){ p = 0; for(int i = 1;i <= w;i++) tp[++p] = sl - w + i; for(int i = 1; i <= sl; i++) if(sa[i] > w) tp[++p] = sa[i] - w; radixSort(); swap(tp,rak); rak[sa[1]] = p = 1; for(int i = 2; i <= sl; i++) rak[sa[i]] = (tp[sa[i]] == tp[sa[i - 1]] && tp[sa[i] + w] == tp[sa[i - 1] + w]) ? p : ++p; } } void make_st(){ int range = lg[sl]; //'('的数目多 if(lr_cnt[sl] > 0){ for(int i = 1;i <= sl;i++) f[i][0] = lr_cnt[i]; for(int i = 1;i <= range;i++) for(int j = 1;j + (1<<i) - 1<= sl;j++) f[j][i] = min(f[j][i-1],f[j+(1<<(i-1))][i-1]); }else{ //')'的数目多 for(int i = 1;i <= sl;i++) f[i][0] = rl_cnt[i]; for(int i = 1;i <= range;i++) for(int j = 1;j + (1<<i) - 1<= sl;j++) f[j][i] = max(f[j][i-1],f[j+(1<<(i-1))][i-1]); } } int query(int l,int r){ int range = lg[r-l+1]; if(lr_cnt[sl] > 0) return min(f[l][range], f[r - (1 << range) + 1][range]); else return max(f[l][range],f[r-(1<<range)+1][range]); } int main(){ scanf("%s",s+1); sl = strlen(s+1); for(int i = 1;i <= sl;i++) s[i + sl] = s[i]; sl <<= 1; //长度翻倍，注意后面用到时要/2得到原长 build_sa(); //lr_cnt为前缀和，rl_cnt为后缀和 for(int i = 1;i <= sl;i++) lr_cnt[i] = lr_cnt[i - 1] + ((s[i] == '(') ? 1 : -1); for(int i = sl;i;i--) rl_cnt[i] = rl_cnt[i + 1] + ((s[i] == '(') ? 1 : -1); //预处理log2数组 for(int i = 2;i <= sl;i++) lg[i] = lg[i-1] + (i == (1<<(lg[i-1]+1))); make_st(); //l_fill是在前端补全'('的数目,r_fill是在末尾补全')'的数目（其中一个为0） int l_fill = 0,r_fill = 0,ans_pos; if(lr_cnt[sl] > 0) r_fill = lr_cnt[sl]/2; //因为序列翻倍，所以得/2 else l_fill = abs(lr_cnt[sl]/2); for(int i = 1;i <= sl;i++){ //获得排名为i的后缀左端点在原串位置 int p = sa[i]; if(p > sl/2) continue; //res查询区间最值 int res = query(p,p + sl/2 -1); if(lr_cnt[sl] > 0){ if(res - lr_cnt[p - 1] < 0) continue; }else{ if(res - rl_cnt[p + sl / 2] > 0) continue; } ans_pos = p; break; } for(int i = 1; i <= l_fill; i++) printf("("); for(int i = ans_pos;i <= ans_pos + sl/2 - 1;i++) printf("%c",s[i]); for(int i = 1; i <= r_fill; i++) printf(")"); return 0; }