1149C - Tree Generator™ - CodeForces Solution

#include <cstdio>
#include <iostream>
#include <cstring>
#define lson p << 1
#define rson p << 1 | 1
using namespace std;
const int N = 2e5 + 5;

int n, m;
char s[N];

struct node {
	int l, r, sum;
	int lmx, lmn, rmx, rmn;
	int lv, rv, mx;
} t[N << 2];
void pushup(int p) {
	t[p].sum = t[lson].sum + t[rson].sum;
	t[p].lmx = max(t[lson].lmx, t[lson].sum + t[rson].lmx);
	t[p].lmn = min(t[lson].lmn, t[lson].sum + t[rson].lmn);
	t[p].rmx = max(t[rson].rmx, t[rson].sum + t[lson].rmx);
	t[p].rmn = min(t[rson].rmn, t[rson].sum + t[lson].rmn);
	t[p].lv = max(t[lson].lv, max(t[rson].lv - t[lson].sum, t[rson].lmx + t[lson].rmx - (t[lson].sum - t[lson].rmx)));
	t[p].rv = max(t[rson].rv, max(t[lson].rv + t[rson].sum, t[rson].sum - t[rson].lmn - (t[lson].rmn + t[rson].lmn)));
	t[p].mx = max(max(t[lson].mx, t[rson].mx), max(t[lson].rv + t[rson].lmx, t[rson].lv - t[lson].rmn));
}
void build(int p, int l, int r) {
	t[p].l = l, t[p].r = r;
	if (l == r) {
		if (s[l] == '(') t[p].sum = t[p].lmx = t[p].rmx = 1;
		else t[p].sum = t[p].lmn = t[p].rmn = -1;
		t[p].lv = t[p].rv = t[p].mx = 1;
		return;
	}
	int mid = l + r >> 1;
	build(lson, l, mid), build(rson, mid + 1, r);
	pushup(p);
}
void update(int p, int x, int d) {
	if (t[p].l == t[p].r) {
		t[p].lmx = t[p].lmn = t[p].rmx = t[p].rmn = 0;
		if (d > 0) t[p].sum = t[p].lmx = t[p].rmx = 1;
		else t[p].sum = t[p].lmn = t[p].rmn = -1;
		return;
	}
	int mid = t[p].l + t[p].r >> 1;
	if (x <= mid) update(lson, x, d);
	else update(rson, x, d);
	pushup(p);
}

int main() {
	scanf("%d %d %s", &n, &m, s + 1), n = (n - 1) * 2;
	build(1, 1, n);
	printf("%d\n", t[1].mx);
	while (m--) {
		int x, y;
		scanf("%d %d", &x, &y);
		if (s[x] == s[y]) {printf("%d\n", t[1].mx); continue;}
		swap(s[x], s[y]);
		update(1, x, s[x] == '(' ? 1 : -1);
		update(1, y, s[y] == '(' ? 1 : -1);
		printf("%d\n", t[1].mx);
	}
	return 0;
}