Codeforces 1149C 线段树 LCA

题意：给你一个括号序列，这个括号序列将确定一颗二叉树。有q次询问，每次询问输出这颗树的直径。

思路：https://blog.csdn.net/Huah_2018/article/details/89788074

代码：

#include <bits/stdc++.h>

#define ls (x << 1)

#define rs ((x << 1) | 1)

using namespace std;

const int maxn = 200010;

char s[maxn];

struct SegmentTree {

	int mx, mi, lmx, rmx, sum, ans;

	void init(int x) {

		mx = x, mi = x, lmx = -x, rmx = -x, sum = x, ans = 0;

	};

};

SegmentTree tr[maxn * 4];

void pushup(int x) {

	int k = x;

	tr[x].mx = max(tr[ls].mx, tr[rs].mx + tr[ls].sum);

	tr[x].mi = min(tr[ls].mi, tr[rs].mi + tr[ls].sum);

	tr[x].lmx = max(tr[ls].lmx, tr[rs].lmx - tr[ls].sum);

	tr[x].lmx = max(tr[x].lmx, tr[ls].mx - 2 * (tr[rs].mi + tr[ls].sum));

	tr[x].rmx = max(tr[ls].rmx, tr[rs].rmx - tr[ls].sum);

	tr[x].rmx = max(tr[x].rmx, tr[rs].mx - 2 * tr[ls].mi + tr[ls].sum);

	tr[x].sum = tr[ls].sum + tr[rs].sum;

	tr[x].ans = max(tr[ls].ans, tr[rs].ans);

	tr[x].ans = max(tr[x].ans, max(tr[ls].lmx + tr[rs].mx + tr[ls].sum, tr[rs].rmx + tr[ls].mx - tr[ls].sum));

}

void build(int x, int l, int r) {

	if(l == r) {

		tr[x].init(s[l] == '(' ? 1 : -1);

		return;

	}

	int mid = (l + r) >> 1;

	build(ls, l, mid);

	build(rs, mid + 1, r);

	pushup(x);

}

void update(int x, int l, int r, int pos) {

	if(l == r) {

		tr[x].init(s[l] == '(' ? 1 : -1);

		return;

	}

	int mid = (l + r) >> 1;

	if(pos <= mid) update(ls, l, mid, pos);

	else update(rs, mid + 1, r, pos);

	pushup(x);

}

int main() {

	int n, T;

	scanf("%d%d", &n, &T);

	n = 2 * n - 2;

	int u, v;

	scanf("%s",s + 1);

	build(1, 1, n);

	printf("%d\n", tr[1].ans);

	while(T--) {

		scanf("%d%d", &u, &v);

		swap(s[u], s[v]);

		update(1, 1, n, u);

		update(1, 1, n, v);

		printf("%d\n", tr[1].ans);

	}

}