本文共 2568 字，大约阅读时间需要 8 分钟。

题目

思路

直径 很容易 让人联想到线段树。为何？就是那个经典的性质，$S+T$ 的直径的两个端点，必然是 $S$ 直径的端点或 $T$ 直径的端点。

问题就是括号序列怎么计算距离罢了。然而这是很简单的，就是欧拉序基操：左右括号抵消。所以剩下的就是 ))))))((( 。然后就可以合并了。

代码

#include 
   
    #include 
    
     #include 
     
      using namespace std;inline int readint(){   	int a = 0; char c = getchar(), f = 1;	for(; c<'0'||c>'9'; c=getchar())		if(c == '-') f = -f;	for(; '0'<=c&&c<='9'; c=getchar())		a = (a<<3)+(a<<1)+(c^48);	return a*f;}const int MaxN = 200005;struct XEZ{   	int a, b; // length of two parts	XEZ(int A,int B):a(A),b(B){    }	XEZ(){    a = b = 0; }	XEZ operator + (const XEZ &t) const {   		return XEZ(			a+max(t.a-b,0),			t.b+max(b-t.a,0)		);	}	bool operator < (const XEZ &t) const {   		return a+b < t.a+t.b;	}};// 0/1: L/R    store two sides of diameterXEZ val[MaxN<<2][2][2];XEZ all[MaxN<<2]; // the whole rangeint ans[MaxN<<2]; // save ansvoid pushUp(int o){   	int li = 0, ri = 0;	XEZ sy = val[o<<1][1][li]		+ val[o<<1|1][0][ri];	for(int i=0; i<2; ++i)	for(int j=0; j<2; ++j){   		XEZ now = val[o<<1][1][i]			+ val[o<<1|1][0][j];		if(sy < now){   			sy = now; // maximum			li = i, ri = j;		}	}	ans[o] = sy.a+sy.b; // calc	val[o][0][0] = val[o<<1][0][li];	val[o][0][1] = all[o<<1]		+ val[o<<1|1][0][ri];	val[o][1][1] = val[o<<1|1][1][ri];	val[o][1][0] = val[o<<1][1][li]		+ all[o<<1|1]; // complete	all[o] = all[o<<1]+all[o<<1|1];	// what if not cross?	if(ans[o] < ans[o<<1]){   		ans[o] = ans[o<<1];		for(int j=0; j<2; ++j)			val[o][0][j] = val[o<<1][0][j];		for(int j=0; j<2; ++j)			val[o][1][j] = val[o<<1][1][j]				+ all[o<<1|1];	}	if(ans[o] < ans[o<<1|1]){   		ans[o] = ans[o<<1|1];		for(int j=0; j<2; ++j)			val[o][1][j] = val[o<<1|1][1][j];		for(int j=0; j<2; ++j)			val[o][0][j] = all[o<<1]				+ val[o<<1|1][0][j];	}	}char str[MaxN]; int n;void single(int o,int l,int r){   	all[o] = XEZ(		str[l] == ')',		str[r] == '('	);	val[o][1][0] = all[o];	val[o][0][1] = all[o];}void build(int o=1,int l=1,int r=n){   	if(l == r) return single(o,l,r);	build(o<<1,l,(l+r)>>1);	build(o<<1|1,(l+r)/2+1,r);	pushUp(o);}void modify(int qid,char c,int o=1,int l=1,int r=n){   	if(l == r){    // == qid		str[l] = c;		return single(o,l,r);	}	if(qid <= ((l+r)>>1))		modify(qid,c,o<<1,l,(l+r)>>1);	else modify(qid,c,o<<1|1,(l+r)/2+1,r);	pushUp(o);}int main(){   	n = (readint()-1)<<1;	int q = readint();	scanf("%s",str+1);	build(); // all in silence	printf("%d\n",ans[1]);	for(int a,b; q; --q){   		a = readint(), b = readint();		if(str[a] != str[b]){   			int zxy = str[a]+str[b];			modify(a,zxy-str[a]);			modify(b,zxy-str[b]);		}		printf("%d\n",ans[1]);	}	return 0;}