题目

你有一个由大写字母 $A$ 和 $B$ 构成的长度为 $n$ 的基因序列 $s$ 。每一次操作把所有子串 $BA$ 替换为 $AB$ ，若干次后基因序列可以有序，即如同 $AAA\dots BBB$ 的形式，你想要知道这个最小次数。

但是这个问题太简单了，你决定加入修改。你现在有 $q$ 次修改，每一次（永久地）把基因序列 $s$ 的一个区间 $[l,r]$ 内所有 $\texttt{A}$ 变为 $\texttt{B}$ ， $\texttt{B}$ 变为 $\texttt{A}$ 。然后再修改后询问你 $\texttt{B}+s+\texttt{A}$ （加法表示拼接）至少需要多少次操作变得有序。

$1\leq n,q\leq 2\times 10^5,0\leq l\leq r< n$ 。

题解

线段树维护，对于每个节点维护正反两种情况。

const int N = 2e5 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, q;
	char s[N];
	struct node {
		int x, y;
		node (int x = 0, int y = 0): x(x), y(y) {}
	};
	node operator + (node a, node b) {
		int z = min(a.y, b.x);
		return node(a.x + b.x - z, a.y + b.y - z);
	}
	struct SegmentTree {
		struct Tree {
			node ori, chd;
			int l, r;
			bool lzy;
		} t[N << 2];
#define lson (p << 1)
#define rson (p << 1 | 1)
		void pushup (int p) {
			t[p].ori = t[lson].ori + t[rson].ori;
			t[p].chd = t[lson].chd + t[rson].chd;
		}
		void build (int p, int l, int r) {
			t[p].l = l, t[p].r = r;
			if (t[p].l == t[p].r) {
				t[p].ori = node(s[l] == 'B', s[l] == 'A');
				t[p].chd = node(s[l] == 'A', s[l] == 'B');
				return ;
			}
			int mid = l + r >> 1;
			build (lson, l, mid);
			build (rson, mid + 1, r);
			pushup(p);
		}
		void swp(int p) {
			swap (t[p].ori, t[p].chd);
			t[p].lzy ^= 1;
		}
		void pushdown (int p) {
			if (!t[p].lzy) return;
			t[p].lzy = 0;
			swp(lson); swp(rson);
		}
		void modify (int p, int l, int r) {
			if (l <= t[p].l && t[p].r <= r) { swp(p); return; }
			pushdown(p);
			int mid = t[p].l + t[p].r >> 1;
			if (l <= mid) modify (lson, l, r);
			if (mid < r) modify (rson, l, r);
			pushup(p);
		}
	} sgt;
	int main () {
		n = Read() + 2; cin >> (s + 2);
		s[1] = 'B', s[n] = 'A';
		sgt.build(1, 1, n);
		for (int q = Read(); q--; ) {
			int l = Read() + 2, r = Read() + 2;
			sgt.modify (1, l, r);
			printf ("%d\n", n - 1 - (n - sgt.t[1].ori.x - sgt.t[1].ori.y) / 2);
		}
		return 0;
	}
}

int main () {
	string str = "medium";
	freopen((str + ".in").c_str(), "r", stdin);
	freopen((str + ".out").c_str(), "w", stdout);
	Main::main();
	return 0;
}