发现题解里的维护前后缀最大最小值的做法都是感性理解，所以我就来写个证明。
将 ( 看做 \(-1\)，) 看做 \(1\)，首先几个变量：
- \(n\) 代表括号序列的长度。
- \(a_i\) 代表前缀和。
- \(b_i\) 代表后缀和。
- \(mxa\) 代表 \(\max_{i=1}^n \left \{ a_i \right \}\)。
- \(mxb\) 代表 \(\max_{i=1}^n \left \{\left | b_i \right | \right \}\)。
结论1： 一个括号序列是合法的等价于 \(∀i\in \left [1,n\right ]\)，\(a_i\le0\) 且 \(∀i\in \left [1,n\right ]\)，\(b_i\ge0\)。
证明1： 先证充分性，反证，若 \(∃i\in \left [1,n\right ]\)，\(a_i>0\)，那么就会出现 ) 使它前面没有更多的 ( 和它匹配。\(b\) 同理。再证必要性，满足上述条件就说明在任何位置都不会存在 ) 前面没有 ( 来和它匹配，( 后面没有 ) 和它匹配。
结论2： 若要使 \(a\) 不存在正数，那么 \(a\) 至少需要改变 $\left \lceil \dfrac{mxa}{2} \right \rceil $ 次。若要使 \(b\) 不存在负数，那么 \(b\) 至少需要改变 \(\left \lceil \dfrac{mxb}{2} \right \rceil\) 次。
证明2： 首先，对于 \(i\)，若它是正数，那么将它变为非正数至少需要改变它及它之前中的 $\left \lceil \dfrac{a_i}{2} \right \rceil $ 个字符（一次改变使 \(1\) 变成 \(-1\)，即使 \(a_i\) 减去 \(2\)），那么总花费不会小于 $\left \lceil \dfrac{mxa}{2} \right \rceil $,我们设 \(p\) 满足 \(p\in \left [1,n\right ]\) 且 \(a_p=mxa\)，我们来考虑除了 \(p\) 之外的某个位置 \(j\) 的花费：
- \(j<p\):只需要将这 \(\left \lceil \dfrac{mxa}{2} \right \rceil\) 个操作从最左端开始往右依次使用，那么就一定能满足 \(j\)。
- \(j>p\):显然 \(p\) 满足了 \(j\) 也满足。
所以改变次数即为 $\left \lceil \dfrac{mxa}{2} \right \rceil \(。\)b$ 同理。
结论3： 若 \(p\) 满足 \(p\in \left [0,n\right ]\) 且 \(a_p=mxa\) 那么 \(\left | b_{i+1} \right | =mxb\)（将 \(a_0\) 与 \(b_{n+1}\) 看做 \(0\)）。
证明3： 简单地推下式子：
\[b_{p+1}= n-a_p= n-mxa= n-\max _{i=0}^n \left \{ a_i \right \} = \min _{i=0}^{n} \left \{ n-a_i \right \} = \min _{i=1}^{n+1}\left \{ b_i \right \} = mxb \]结论4： 将括号序列变成合法（即使 \(a\) 不存在正数，使 \(b\) 不存在负数）的最小操作次数为 \(\left \lceil \dfrac{mxa}{2} \right \rceil+\left \lceil \dfrac{mxb}{2} \right \rceil\) 。
证明4： 容易知道答案不会比 \(\left \lceil \dfrac{mxa}{2} \right \rceil+\left \lceil \dfrac{mxb}{2} \right \rceil\) 小，那么我们证明一定存在构造方案使得答案就是这个式子。记 \(p\) 满足 \(p\in \left [0,n\right ]\) 且 \(a_p=mxa\)，考虑是否有可能在所有操作之后，\(a\) 或 \(b\) 不合法了。容易知道 \(mxa\) 和 \(mxb\) 奇偶性相同，分类讨论：
- 若 \(mxa\) 与 \(mxb\) 都是偶数，若我们先让 \(b\) 变成合法的，那么在操作后，\(b_{p+1}=0\) 并且 \(∀i\in \left [p+1,n+1\right ]\)，\(b_i\ge0\)，那么有 \(∀i\in \left [p+1,n+1\right ]\)，\(b_{p+1}-b_i\le0\)，再让 \(a\) 变为合法的，在 \(p\) 及之前的括号只会在让 \(a\) 合法的过程中改变，而在后面的位置，由于只会加上非正数，所以 \(a\) 仍然合法。
- 类似。
所以就证明出了答案就是 \(\left \lceil \dfrac{mxa}{2} \right \rceil+\left \lceil \dfrac{mxb}{2} \right \rceil\)。剩下的内容和其他题解就都一样了qwq。
code：
点击查看代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<cstdlib>
#include<ctime>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
const int N=1e5+10;
int ls[N],rs[N],sz[N],wei[N],lmx[N],rmx[N],lmi[N],rmi[N],val[N],sum[N],lz[N],lzs[N],lzv[N],tot,rt;
int New(int v)
{
wei[++tot]=rand();sz[tot]=1;
if(v==1)lmx[tot]=rmx[tot]=1; else lmi[tot]=rmi[tot]=-1;
sum[tot]=val[tot]=v;
return tot;
}
void pushup(int p)
{
sz[p]=sz[ls[p]]+sz[rs[p]]+1,sum[p]=sum[ls[p]]+sum[rs[p]]+val[p];
lmx[p]=max(lmx[ls[p]],sum[ls[p]]+val[p]+lmx[rs[p]]);
lmi[p]=min(lmi[ls[p]],sum[ls[p]]+val[p]+lmi[rs[p]]);
rmx[p]=max(rmx[rs[p]],sum[rs[p]]+val[p]+rmx[ls[p]]);
rmi[p]=min(rmi[rs[p]],sum[rs[p]]+val[p]+rmi[ls[p]]);
}
void pushdown(int p)
{
if(lz[p])
{
lz[ls[p]]=lz[rs[p]]=lz[p];
lzs[ls[p]]=lzv[ls[p]]=lzs[rs[p]]=lzv[rs[p]]=0;
val[ls[p]]=val[rs[p]]=lz[p];
if(lz[p]==1)
{
sum[ls[p]]=sz[ls[p]],sum[rs[p]]=sz[rs[p]];
lmx[ls[p]]=rmx[ls[p]]=sz[ls[p]];
lmx[rs[p]]=rmx[rs[p]]=sz[rs[p]];
lmi[ls[p]]=rmi[ls[p]]=lmi[rs[p]]=rmi[rs[p]]=0;
}
else
{
sum[ls[p]]=-sz[ls[p]],sum[rs[p]]=-sz[rs[p]];
lmi[ls[p]]=rmi[ls[p]]=-sz[ls[p]];
lmi[rs[p]]=rmi[rs[p]]=-sz[rs[p]];
lmx[ls[p]]=rmx[ls[p]]=lmx[rs[p]]=rmx[rs[p]]=0;
}
lz[p]=0;
}
if(lzs[p])
{
lzs[ls[p]]^=1,lzs[rs[p]]^=1;
swap(ls[ls[p]],rs[ls[p]]),swap(ls[rs[p]],rs[rs[p]]);
swap(lmx[ls[p]],rmx[ls[p]]),swap(lmi[ls[p]],rmi[ls[p]]);
swap(lmx[rs[p]],rmx[rs[p]]),swap(lmi[rs[p]],rmi[rs[p]]);
lzs[p]=0;
}
if(lzv[p])
{
lzv[ls[p]]^=1,lzv[rs[p]]^=1;
val[ls[p]]*=-1,val[rs[p]]*=-1;
sum[ls[p]]*=-1,sum[rs[p]]*=-1;
swap(lmx[ls[p]],lmi[ls[p]]),lmx[ls[p]]*=-1,lmi[ls[p]]*=-1;
swap(rmx[ls[p]],rmi[ls[p]]),rmx[ls[p]]*=-1,rmi[ls[p]]*=-1;
swap(lmx[rs[p]],lmi[rs[p]]),lmx[rs[p]]*=-1,lmi[rs[p]]*=-1;
swap(rmx[rs[p]],rmi[rs[p]]),rmx[rs[p]]*=-1,rmi[rs[p]]*=-1;
lzv[p]=0;
}
}
int merge(int x,int y)
{
if(!x||!y)return x|y;
if(wei[x]<wei[y]){pushdown(x),rs[x]=merge(rs[x],y),pushup(x);return x;}
else {pushdown(y),ls[y]=merge(x,ls[y]),pushup(y);return y;}
}
void split(int p,int &x,int &y,int k)
{
if(!p){x=y=0;return;}
pushdown(p);
if(sz[ls[p]]<k)x=p,split(rs[x],rs[x],y,k-sz[ls[p]]-1);
else y=p,split(ls[y],x,ls[y],k);
pushup(p);
}
void ins(int v){rt=merge(rt,New(v));}
int n,Q;
char str[N];
void spl(int l,int r,int &x,int &y,int &z){split(rt,y,z,r),split(y,x,y,l-1);}
void mer(int x,int y,int z){rt=merge(x,merge(y,z));}
int main()
{
srand(time(0));
cin>>n>>Q;
scanf("%s",str+1);
rep(i,1,n)ins(str[i]==')'?1:-1);
while(Q--)
{
cin>>str[1];int l,r;
if(str[1]=='R')
{
rep(i,1,6)cin>>str[1];
cin>>l>>r>>str[1];
int v=(str[1]==')'?1:-1);
int x,y,z;
spl(l,r,x,y,z);
lz[y]=val[y]=v;
lzs[y]=lzv[y]=0;
if(v==1)sum[y]=lmx[y]=rmx[y]=sz[y],lmi[y]=rmi[y]=0;
else sum[y]=lmi[y]=rmi[y]=-sz[y],lmx[y]=rmx[y]=0;
mer(x,y,z);
}
else if(str[1]=='S')
{
rep(i,1,3)cin>>str[1];
cin>>l>>r;
int x,y,z;
spl(l,r,x,y,z);
lzs[y]^=1;
swap(ls[y],rs[y]),swap(lmx[y],rmx[y]),swap(lmi[y],rmi[y]);
mer(x,y,z);
}
else if(str[1]=='I')
{
rep(i,1,5)cin>>str[1];
cin>>l>>r;
int x,y,z;
spl(l,r,x,y,z);
lz[y]*=-1,lzv[y]^=1;
sum[y]*=-1,val[y]*=-1;
swap(lmx[y],lmi[y]),lmx[y]*=-1,lmi[y]*=-1;
swap(rmx[y],rmi[y]),rmx[y]*=-1,rmi[y]*=-1;
mer(x,y,z);
}
else
{
rep(i,1,4)cin>>str[1];
cin>>l>>r;
int x,y,z;
spl(l,r,x,y,z);
printf("%d\n",lmx[y]/2+(lmx[y]&1)+abs(rmi[y])/2+(abs(rmi[y])&1));
mer(x,y,z);
}
}
return 0;
}