对$t$的操作即在$t$中插入一对括号，逆过程也即删除一对括号
换言之，$s$能被$t$得到当且仅当通过删除$s$中若干对括号可以得到$t$，问题也即求$\min t$
结论：通过删除$s$中若干个合法子串（指合法括号序列）可以得到$\min t$
考虑原来得到$\min t$的过程，对于其中每一对删除的括号，两个括号中间的部分必然也被删除（否则可以让删除的左括号更右或右括号更左，显然字典序不增）
进一步的，考虑一个极长删除区间，其中的括号删除时，对应的括号也总在此区间内（否则不极长），因此也即构成了一个合法括号序列，将这些区间分别删除即可
另一方面，合法子串显然也可以拆解为若干对括号，因此不妨以此为问题
另外，合法括号序列中删除若干个合法子串后显然仍合法，即删除顺序不影响（任意）
考虑dp，令$ans_{i}$为$s[i,|s|]$的答案，不难得到$ans_{i}=\min(s_{i}+ans_{i+1},\min_{s[i,j)合法}ans_{j})$
记$i$向右最短非空合法子串为$s[i,next_{i})$，注意到$s[i,j)$合法则$s[next_{i},j)$也合法，即$ans_{next_{i}}$已经包含后者，不妨仅转移$j=next_{i}$，也即$ans_{i}=\min(s_{i}+ans_{i+1},ans_{next_{i}})$
下面，考虑如何实现此过程：
建议一棵树，以$n+1$为根，$i$到根路径上的字符构成$ans_{i}$（类似于trie树）
考虑求$ans_{i}$，初始以$s_{i}+ans_{i+1}$为转移，即将$i$作为$i+1$的儿子，边上的字符为$s_{i}$
接下来，若$next_{i}$到根路径的字符串比$i$小，则将$i$作为$next_{i}$父亲的儿子，边上的字符为$s_{next_{i}}$
关于比较，注意到总是新增叶子，使用倍增+哈希找到第一个不同的位置即可
时间复杂度为$o(n\log n)$，可以通过
（代码实现成了$o(n\log^{2}n)$，直接在倍增中比较即可去掉二分）
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 300005 4 #define L 19 5 #define ull unsigned long long 6 int n,st[N],nex[N],pos[N],dep[N],fa[N][L]; 7 ull mi[N],Hash[N][L]; 8 char s[N]; 9 int get_pos(int k,int d){ 10 for(int i=0;i<L;i++) 11 if (d&(1<<i))k=fa[k][i]; 12 return k; 13 } 14 ull get_Hash(int k,int d){ 15 ull ans=0; 16 for(int i=0,s=0;i<L;i++) 17 if (d&(1<<i)){ 18 ans=ans+Hash[k][i]*mi[s]; 19 k=fa[k][i],s|=(1<<i); 20 } 21 return ans; 22 } 23 void add(int k,int f,int p){ 24 pos[k]=p,dep[k]=dep[f]+1; 25 fa[k][0]=f,Hash[k][0]=p; 26 for(int i=1;i<L;i++){ 27 fa[k][i]=fa[fa[k][i-1]][i-1]; 28 Hash[k][i]=Hash[k][i-1]+Hash[fa[k][i-1]][i-1]*mi[1<<i-1]; 29 } 30 } 31 bool cmp(int x,int y){ 32 int l=0,r=min(dep[x],dep[y]); 33 while (l<r){ 34 int mid=(l+r+1>>1); 35 if (get_Hash(x,mid)==get_Hash(y,mid))l=mid; 36 else r=mid-1; 37 } 38 x=get_pos(x,l),y=get_pos(y,l); 39 return pos[x]<pos[y]; 40 } 41 int main(){ 42 mi[0]=1; 43 for(int i=1;i<N;i++)mi[i]=3*mi[i-1]; 44 scanf("%s",s+1),n=strlen(s+1); 45 for(int i=1;i<=n;i++) 46 if (s[i]=='(')st[++st[0]]=i; 47 else{ 48 if (st[0])nex[st[st[0]--]]=i+1; 49 } 50 dep[0]=-1; 51 for(int i=n;i;i--){ 52 add(i,i+1,(s[i]==')')+1); 53 if ((nex[i])&&(cmp(nex[i],i)))add(i,fa[nex[i]][0],pos[nex[i]]); 54 } 55 for(int i=1;fa[i][0];i=fa[i][0]){ 56 if (pos[i]==1)printf("("); 57 else printf(")"); 58 } 59 printf("\n"); 60 return 0; 61 }