题目大意

给定长度为 $n$ 的序列 $a$ 和 $01$ 序列 $b$，对于 $u<v$ 的二元组 $(u,v)$ 能够匹配当且仅当 $b_u=0$ 且 $b_v=1$。试求所有匹配中，$a_u=a_v$ 数量最多的匹配边情况下，匹配的最大值是多少？给定 $m$ 次修改，每次修改：

• $\tt x\ p\ q$：$a_x:=p,b_x:=q$。

数据范围：$1\le n,m\le 2\times 10^5$，$1\le a_i\le n$，$0\le b_i\le 1$。

思路

对于这种数据结构题，通常考虑不带修怎么做？这里不带修是经典贪心，对于每种颜色，从左往右扫其出现位置，遇到 $b_i=1$ 则判定前面是否存在未匹配的 $b_j=0$ 的位置，若存在则选择最大的 $j$ 匹配。这样的道理在于，最后剩余的 $111...1000...0$ 结构 $0$ 的位置尽可能靠前，$1$ 的位置尽可能靠后。这样就得到 $O(nm)$ 做法。

接下来，考虑带修怎么做？这个分析单点修后对 $111...1000...0$ 结构的影响，可以拆解为插入 / 删除元素，这里自然能想到去维护这个变化量，每次找到变化的节点，不过这样就有些麻烦了（这也是大部分题解的做法）。仔细分析一下变化量，会发现实际上两个下标位置集合的对称差（变化）只有 $1$，因为相当于若干个节点匹配点向右平移，最后只有一个空出来，如果这个与其他发生匹配，相当于删除元素；如果未发生匹配，则相当于新加元素（建议读者自行画图分析，这里可能说不太明白）。

既然，变化量只有 $1$，那有什么好办法呢？异或！两个集合对称差是 $1$ 的时候，可以通过异或将这个元素查找出来。于是，只需要用单侧递归线段树将化简后的下标异或和求出来即可。

时间复杂度：$O(q\log^2 n)$（不过跑的比很多单 $\log$ 都快，常数并不大）。

空间复杂度：$O(n\log n)$。

代码

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

const int N = 2E5 + 10;

int n, m, base, idx;
int a[N], b[N];
struct node {
	int ls, rs;
	int x, y, z;
	int a, b;
}tr[N * 40];
#define ls(u) tr[u].ls
#define rs(u) tr[u].rs
int rt[N], mask[N];
set<int> pos[N];

int calc1(int u, int k) {
	if (!k) return tr[u].a;
	if (k == tr[u].x) return 0;
	if (tr[ls(u)].x >= k) return calc1(ls(u), k) ^ tr[ls(u)].a ^ tr[u].a;
	return calc1(rs(u), k - tr[ls(u)].x + tr[ls(u)].y);
}

int calc2(int u, int k) {
	if (!k) return tr[u].b;
	if (k == tr[u].y) return 0;
	if (tr[rs(u)].y >= k) return calc2(rs(u), k) ^ tr[rs(u)].b ^ tr[u].b;
	return calc2(ls(u), k - tr[rs(u)].y + tr[rs(u)].x);
}

void pushup(int u) {
	if (tr[ls(u)].y <= tr[rs(u)].x) {
		tr[u].x = tr[ls(u)].x + tr[rs(u)].x - tr[ls(u)].y;
		tr[u].y = tr[rs(u)].y;
		tr[u].z = tr[ls(u)].z + tr[rs(u)].z + tr[ls(u)].y;
		tr[u].a = calc1(rs(u), tr[ls(u)].y) ^ tr[ls(u)].a;
		tr[u].b = tr[rs(u)].b;
	} else {
		tr[u].x = tr[ls(u)].x, tr[u].y = tr[ls(u)].y - tr[rs(u)].x + tr[rs(u)].y;
		tr[u].z = tr[ls(u)].z + tr[rs(u)].z + tr[rs(u)].x;
		tr[u].a = tr[ls(u)].a;
		tr[u].b = calc2(ls(u), tr[rs(u)].x) ^ tr[rs(u)].b;
	}
}

void update(int &u, int l, int r, int x, node t) {
	if (!u) u = ++ idx;
	if (l == r) { tr[u] = t; return; }
	int mid = l + r >> 1;
	if (mid >= x) update(tr[u].ls, l, mid, x, t);
	else update(tr[u].rs, mid + 1, r, x, t);
	pushup(u);
}

array<int, 3> zkw[N * 4];

array<int, 3> operator* (array<int, 3> x, array<int, 3> y) {
	if (x[1] <= y[0]) return {x[0] + y[0] - x[1], y[1], x[2] + y[2] + x[1]};
	else return {x[0], x[1] - y[0] + y[1], x[2] + y[2] + y[0]};
}

int res = 0, cnt = 0;
void work(int i, node j) {
	res -= tr[rt[a[i]]].z;
	update(rt[a[i]], 1, n, i, j);
	res += tr[rt[a[i]]].z;
	int nmask = tr[rt[a[i]]].a ^ tr[rt[a[i]]].b, np = mask[a[i]] ^ nmask;
	cnt ++;
	if (pos[a[i]].count(np)) pos[a[i]].erase(np), zkw[np + base] = {0, 0, 0};
	else pos[a[i]].insert(np), zkw[np + base] = {b[np], !b[np], 0};
	for (int k = np + base >> 1; k; k >>= 1)
		zkw[k] = zkw[k << 1] * zkw[k << 1 | 1];
	mask[a[i]] = nmask;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> n >> m, base = (1 << __lg(n) + 1) - 1;

	for (int i = 1; i <= n; i ++) cin >> a[i];
	for (int i = 1; i <= n; i ++) cin >> b[i];

	for (int i = 1; i <= n; i ++) work(i, {0, 0, b[i], !b[i], 0, b[i] * i, (!b[i]) * i});
	cout << res + zkw[1][2] << '\n';

	while (m -- ) {
		int x, p, q;
		cin >> x >> p >> q;

		work(x, {0, 0, 0, 0, 0, 0, 0});
		a[x] = p, b[x] = q;
		work(x, {0, 0, b[x], !b[x], 0, b[x] * x, (!b[x]) * x});

		cout << res + zkw[1][2] << '\n';
	}

	return 0;
}