这不但打了 TM 而且还是世界知名商标，可能受法律保护哦

一道非常惊喜的线段树题。

给定一颗树, 用 ( 表示下一层， ) 表示上一层，$q$ 次询问，每次交换两个括号，求每次的直径。

从上面的图我们可以得到一个结论：

链是由形如 ))))((((( 的字符串构成的

因为肯定是退上来再深入到另一边，而且链只能一上一下，所以原题目其实等价于要求维护去掉所有匹配括号后长度最长的子串。

令人惊喜的是，可以用线段树来维护。

1. 将在 ( 的权设为 $1$， ) 设为 $-1$, 这样一段区间内数字的和就是多出来的左括号个数，而如果是右括号多出来，则这个值时负的，所以统计个数只需要用连续且靠后的一段减前面一段最大就可以了。

2. 但这个东西直接用线段树维护似乎没有办法做，所以多记录一些信息来尝试合并，记录这两个区间一边顶到头的非常好合并，只需要一边的和再 加/减 另一边顶到这一边的答案就可以了。

3. 所以考虑如何用一边顶到头的答案合并除最后的答案。

   1. 可能是左边或右边原有的答案
   2. 可能是右边最大前缀和加上左边顶到右端点的答案
   3. 可能是右边顶到左端点的答案减去左边最小的后缀

pushup 函数如下

void pushup(int p) {
	tree[p].sum = tree[p+p].sum + tree[p+p+1].sum;
	tree[p].lmax = std::max(tree[p+p].lmax, tree[p+p].sum + tree[p+p+1].lmax);
	tree[p].rmax = std::max(tree[p+p+1].rmax, tree[p+p+1].sum + tree[p+p].rmax);
	tree[p].lmin = std::min(tree[p+p].lmin, tree[p+p].sum + tree[p+p+1].lmin);
	tree[p].rmin = std::min(tree[p+p+1].rmin, tree[p+p+1].sum + tree[p+p].rmin);
	
	tree[p].max1 = std::max(tree[p+p].max1, std::max(tree[p+p+1].max1 - tree[p+p].sum,
				   tree[p+p+1].lmax + tree[p+p].rmax - (tree[p+p].sum - tree[p+p].rmax)));
	tree[p].max2 = std::max(tree[p+p+1].max2, std::max(tree[p+p+1].sum + tree[p+p].max2,
				   tree[p+p+1].sum - tree[p+p+1].lmin - (tree[p+p+1].lmin + tree[p+p].rmin)));
	tree[p].ans = std::max(std::max(tree[p+p].ans, tree[p+p+1].ans), std::max(
				  tree[p+p].max2 + tree[p+p+1].lmax, tree[p+p+1].max1 - tree[p+p].rmin));			   
}

重点解释 max1 的合并， max2 同理

tree[p].max1 = std::max(tree[p+p].max1,   // 可能是左边顶到左端点的答案
	           std::max(tree[p+p+1].max1 - tree[p+p].sum, // 左边全部被当成 ) 的一段，右边靠左最大的减去左边的和
			            tree[p+p+1].lmax + tree[p+p].rmax - (tree[p+p].sum - tree[p+p].rmax)));
		       // 中间一段最大的接起来减去左边剩下的，即 ( 的一段跨越了分界线

如果不是把匹配的都去掉，答案一定会更小，会被更大的答案覆盖，所以不需要特殊判断。

修改和建树都比较常规。