( ext{Description})
( ext{Pre Cheese})
一棵树的括号序列表示了这棵树。左括号代表向下走，右括号是向上走。从根节点开始走。
一个和题目没什么关系的小结论：
一棵树的括号序列长度为 (2 imes (n-1))。
证明：每条边必定可以这样表示 ((......))（因为有去有回嘛）。所以一条边对应两个括号，边条数为 (n-1)，括号序列长度则为 (2 imes (n-1))。
( ext{Solution})
选取从 (u) 到 (v) 的括号序列（其实这个序列只要起点到 (v) 能经过 (u) 即可，但注意到了 (v) 就必须停止（设 (u) 在 (v) 遍历之前）），匹配的括号就消掉，剩下的括号形如 )))(((。则有：
剩余括号个数为 ( ext{dis}(u,v))。
证明：
考虑到 (x) 点时某对括号（假设这对括号代表的边能从上到达 (y)，再回去）的匹配状态。
-
均已出现。(y) 不是 (x) 的祖先或子孙。
-
均未出现。(y) 不是 (x) 的祖先。
-
出现左括号。(y) 是 (x) 的祖先。
我们回来看 (u,v) 的括号序列。
- 能够匹配的括号。对于 (u) 是情况二，对于 (v) 是情况一，则“既不是 (u) 的祖先，也不是 (v) 的的祖先或子孙”。根本不在路径上。
- 左括号。对于 (u) 是情况二，对于 (v) 是情况三，则“不是 (u) 的祖先，但是是 (v) 的的祖先”。在路径上。
- 右括号。对于 (u) 是情况三，对于 (v) 是情况一，则“是 (u) 的祖先，但不是 (v) 的的祖先或子孙”。在路径上（这时肯定不在 (u,v) 的公共祖先上）。
所以结论得证。
那么如何计算呢？
如果要消去匹配的括号，我们马上就会想到给括号赋值：( 为 (1)，) 为 (-1)。但这样就会使 )))((( 的计算费些周折：考虑到剩余括号个数就是 (3-(-3)=6)，我们的答案转化为求相邻两段区间和的差的最大值，可以用线段树维护。
接下来为了方便，设区间的两个左右区间为 (l,r)。
先思考我们要求的相邻两段区间和的差的最大值（令它为 (ans)）该如何合并。首先有 (ans_l,ans_r) 的贡献，其次需要考虑跨区间的情况。我们对提供贡献的数据有这样的要求：
- (l) 选择的区间必须包含 (mid)，(r) 选择的区间必须包含 (mid+1)。
- 因为只能有一个分界点（即相邻两段区间的划分点），不能直接用 (ans) 来贡献，我们必须钦定分界点在 (l/r)。
由此就有了数组的定义：
- (ans)：答案。
- (sum)：区间和。
- (lma)：最大前缀和。
- (rmi)：最小后缀和。
- (ld)：最大含分界点且包含左端点的答案。
- (rd)：最大含分界点且包含右端点的答案。
- (d)：最大含分界点且包含整个区间的答案。
如何维护相信大家都会了。我是真的不想写了。
( ext{Code})
#include <cstdio>
#define rep(i,_l,_r) for(register signed i=(_l),_end=(_r);i<=_end;++i)
#define fep(i,_l,_r) for(register signed i=(_l),_end=(_r);i>=_end;--i)
#define erep(i,u) for(signed i=head[u],v=to[i];i;i=nxt[i],v=to[i])
#define efep(i,u) for(signed i=Head[u],v=to[i];i;i=nxt[i],v=to[i])
#define print(x,y) write(x),putchar(y)
template <class T> inline T read(const T sample) {
T x=0; int f=1; char s;
while((s=getchar())>'9'||s<'0') if(s=='-') f=-1;
while(s>='0'&&s<='9') x=(x<<1)+(x<<3)+(s^48),s=getchar();
return x*f;
}
template <class T> inline void write(const T x) {
if(x<0) return (void) (putchar('-'),write(-x));
if(x>9) write(x/10);
putchar(x%10^48);
}
template <class T> inline T Max(const T x,const T y) {if(x>y) return x; return y;}
template <class T> inline T Min(const T x,const T y) {if(x<y) return x; return y;}
template <class T> inline T fab(const T x) {return x>0?x:-x;}
template <class T> inline T gcd(const T x,const T y) {return y?gcd(y,x%y):x;}
template <class T> inline T lcm(const T x,const T y) {return x/gcd(x,y)*y;}
#include <iostream>
using namespace std;
const int maxn=2e5+5;
int n,m,a[maxn],ans[maxn<<2],sum[maxn<<2],lma[maxn<<2],rmi[maxn<<2],ld[maxn<<2],rd[maxn<<2],d[maxn<<2];
char str[maxn];
void pushUp(int o) {
int ls=(o<<1),rs=(o<<1|1);
sum[o]=sum[ls]+sum[rs];
lma[o]=Max(lma[ls],sum[ls]+lma[rs]);
rmi[o]=Min(rmi[rs],sum[rs]+rmi[ls]);
ld[o]=Max(ld[ls],Max(d[ls]+lma[rs],ld[rs]-sum[ls]));
rd[o]=Max(rd[rs],Max(d[rs]-rmi[ls],sum[rs]+rd[ls]));
d[o]=Max(d[ls]+sum[rs],d[rs]-sum[ls]);
ans[o]=Max(Max(ans[ls],ans[rs]),Max(ld[rs]-rmi[ls],rd[ls]+lma[rs]));
}
void Insert(int o,int l,int r,int pos,int k) {
if(l>pos||r<pos) return;
if(l==r) {
sum[o]=k;
lma[o]=Max(k,0),rmi[o]=Min(k,0);
ld[o]=rd[o]=ans[o]=d[o]=1;
return;
}
int mid=l+r>>1;
Insert(o<<1,l,mid,pos,k); Insert(o<<1|1,mid+1,r,pos,k);
pushUp(o);
}
int main() {
n=read(9)*2-2,m=read(9),scanf("%s",str+1);
rep(i,1,n) {
if(str[i]=='(') a[i]=1;
else a[i]=-1;
Insert(1,1,n,i,a[i]);
}
print(ans[1],'
');
int x,y;
while(m--) {
x=read(9),y=read(9);
if(a[x]==a[y]) {print(ans[1],'
'); continue;}
swap(a[x],a[y]);
Insert(1,1,n,x,a[x]); Insert(1,1,n,y,a[y]);
print(ans[1],'
');
}
return 0;
}