Codeforces 1150E（树、线段树）

要点

括号序列平衡度即树深度的性质
相当于中序遍历，则两点间最浅的地方即是LCA的性质
线段树维护\(d(a) + d(c) - 2*d(lca(a,c))\)，一层层剥，思考维护这个量需要什么，结果维护一大堆。

#include <cstdio>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn = 2e5 + 5;

int n, q;

char s[maxn];

class SegmentTree {

public:

	#define ls (p << 1)

	#define rs (p << 1 | 1)

	struct node {

		int l, r;

		int depth;//its root is s[l]

		int ans;//d(a) + d(c) - 2d(lca(a, c))

		int lmax;//d(a) - 2d(lca(a, c))

		int rmax;//d(c) - 2d(lca(a, c))

		int mxd;//max depth

		int mnd;//min depth

		void init(int val) {

			mxd = mnd = depth = val;

			lmax = rmax = -val;

			ans = 0;

		}

	}t[maxn * 3];

	void Push_up(int p) {

		// b = lca(a, c), a <= b <= c

		t[p].depth = t[ls].depth + t[rs].depth;

		t[p].mxd = max(t[ls].mxd, t[rs].mxd + t[ls].depth);

		t[p].mnd = min(t[ls].mnd, t[rs].mnd + t[ls].depth);

		t[p].lmax = max(t[ls].lmax, t[rs].lmax - t[ls].depth);//a, b both in l or r

		t[p].lmax = max(t[p].lmax, t[ls].mxd - 2 * (t[rs].mnd + t[ls].depth));//a in l and b in r

		t[p].rmax = max(t[ls].rmax, t[rs].rmax - t[ls].depth);//b, c both in l or r

		t[p].rmax = max(t[p].rmax, t[rs].mxd + t[ls].depth - 2 * t[ls].mnd);//b int l and c in r

		t[p].ans = max(t[ls].ans, t[rs].ans);//a,b,c all in l or r

		t[p].ans = max(t[p].ans, max(t[ls].lmax + t[rs].mxd + t[ls].depth, t[ls].mxd + t[rs].rmax - t[ls].depth));//ab in l, c in r || a in l, bc in r

	}

	void Build(int l, int r, int p) {

		t[p].l = l, t[p].r = r;

		if (l == r) {

			t[p].init(s[l] == '(' ? 1 : -1);

			return;

		}

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

		Build(l, mid, ls);

		Build(mid + 1, r, rs);

		Push_up(p);

	}

	void Modify(int l, int r, int p) {

		if (t[p].l == t[p].r) {

			t[p].init(s[l] == '(' ? 1 : -1);

			return;

		}

		int mid = (t[p].l + t[p].r) >> 1;

		if (l <= mid)	Modify(l, r, ls);

		if (mid < r)	Modify(l, r, rs);

		Push_up(p);

	}

}tree;

int main() {

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

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

	n = (n - 1) << 1;

	tree.Build(1, n, 1);

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

	for (int a, b; q; q--) {

		scanf("%d %d", &a, &b);

		if (s[a] != s[b]) {

			swap(s[a], s[b]);

			tree.Modify(a, a, 1);

			tree.Modify(b, b, 1);

		}

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

	}

}

巴特西

Codeforces 1150E（树、线段树）

要点

最新文章

热门文章