题目大意

给定一个长度为 $n$ 的字符序列，初始全是 L。

有 $q$ 次操作，每次将 $a_x$ 在 L 和 R 中切换。

求每次操作后字符串中最长交错序列的长度。

分析

首先需要逐位异或，把交错序列变成相同元素。我想到的是另一种办法，如果 $a_i$ 相对与 $a_{i-1}$ 是变化的，那么 $b_i$ 为 $1$。原问题即被转化为维护最长 $1$ 的个数。

用线段树维护每一层的信息，其中 $l$ 表示左边界上的最长长度，$r$ 表示右边界上的最长长度，$val$ 表示整个区间上的最长长度。

关键在于如何编写 pull 合并信息。

  • 如果整块区域都是 $1$，那么可以和另一块区域合并。
  • 合并后的 $val$ 应该考虑在左边界、右边界、左子树、右子树和中间中取。
struct SegmentTree {
	vector<int> l, r, val;

	int N;
	SegmentTree(int n) {
		N = 2 << std::__lg(n);
		l.resize(N * 2, 0);
		r.resize(N * 2, 0);
		val.resize(N * 2, 0);
	}
	void pull(int p, int len) {
		int ls = p * 2, rs = p * 2 + 1;
		l[p] = l[ls], r[p] = r[rs];
		if (l[ls] == len)
			l[p] += l[rs];
		if (r[rs] == len)
			r[p] += r[ls];
		val[p] = max({l[p], r[p], val[ls], val[rs], r[ls] + l[rs]});
	}
	void modify(int i) {
		i += N;
		l[i] = r[i] = val[i] = !val[i];
		int len = 1;
		for (int k = i / 2; k >= 1; k /= 2, len *= 2) {
			pull(k, len);
		}
	}
};