BZOJ4129: Haruna’s Breakfast 树上带修莫队

Description
给你一棵树。
每次修改一个点。
每次询问两个点之间的mex值。

---

Sample Input
10 10
1 0 1 0 2 4 4 0 1 0
1 2
2 3
2 4
2 5
1 6
6 7
2 8
3 9
9 10
0 7 14
1 6 6
0 4 9
1 2 2
1 1 8
1 8 3
0 10 9
1 3 5
0 10 0
0 7 7

---

Sample Output
0
1
2
2
3

---

学了一下带修莫队
树上莫队，树上带修莫队等算法。。。
好吧，这就是道裸题。。。
首先你树上带修莫队吗。
求mex你可以考虑权值分块来搞一下。

---

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;
int _min(int x, int y) {return x < y ? x : y;}
int _max(int x, int y) {return x > y ? x : y;}
int read() {
	int s = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
	return s * f;
}

struct edge {
	int x, y, next;
} e[110000]; int len, last[51000];
struct node {
	int x, y, last, id;
} q[51000], cg[51000];
int id, dfn[51000], belong[51000], dep[51000];
int ans, a[51000], b[51000], s[51000], A[51000], kk[51000], ll[51000], rr[51000];
int fa[19][51000];
bool v[51000];

bool cmp(node a, node b) {
	if(belong[dfn[a.x]] == belong[dfn[b.x]]) {
		if(belong[dfn[a.y]] == belong[dfn[b.y]]) return a.last < b.last;
		return belong[dfn[a.y]] < belong[dfn[b.y]];
	} return belong[dfn[a.x]] < belong[dfn[b.x]];
}

void ins(int x, int y) {
	e[++len].x = x; e[len].y = y;
	e[len].next = last[x]; last[x] = len;
}

void dfs(int x) {
	dfn[x] = ++id;
	for(int i = 1; (1 << i) <= dep[x]; i++) fa[i][x] = fa[i - 1][fa[i - 1][x]];
	for(int k = last[x]; k; k = e[k].next) {
		int y = e[k].y;
		if(y != fa[0][x]) {
			fa[0][y] = x;
			dep[y] = dep[x] + 1;
			dfs(y);
		}
	}
}

int LCA(int x, int y) {
	if(dep[x] > dep[y]) swap(x, y);
	for(int i = 18; i >= 0; i--) if(dep[y] - dep[x] >= (1 << i)) y = fa[i][y];
	if(x == y) return x;
	for(int i = 18; i >= 0; i--) if(fa[i][x] != fa[i][y]) x = fa[i][x], y = fa[i][y];
	return fa[0][x];
}

void ct(int st, int ed) {
	for(int i = st + 1; i <= ed; i++) {
		int x = cg[i].x;
		if(v[x]) {
			s[a[x]]--;
			if(s[a[x]] == 0) kk[belong[a[x]]]--;
			s[cg[i].y]++;
			if(s[cg[i].y] == 1) kk[belong[cg[i].y]]++;
		} a[x] = cg[i].y;
	}
	for(int i = st; i >= ed + 1; i--) {
		int x = cg[i].x;
		if(v[x]) {
			s[a[x]]--;
			if(s[a[x]] == 0) kk[belong[a[x]]]--;
			s[cg[i].last]++;
			if(s[cg[i].last] == 1) kk[belong[cg[i].last]]++;
		} a[x] = cg[i].last;
	}
}

void bak(int x) {
	if(!v[x]) {
		s[a[x]]++;
		if(s[a[x]] == 1) kk[belong[a[x]]]++;
	} else {
		s[a[x]]--;
		if(s[a[x]] == 0) kk[belong[a[x]]]--;
	} v[x] ^= 1;
}

void solve(int x, int y) {
	while(x != y) {
		if(dep[x] > dep[y]) swap(x, y);
		bak(y); y = fa[0][y];
	}
}

int main() {
	int n = read(), Q = read();
	int m = pow(n, 2.0 / 3);
	for(int i = 1; i <= n; i++) {
		a[i] = read();
		if(a[i] > n) a[i] = n;
		b[i] = a[i];
	}
	for(int i = 1; i < n; i++) {
		int x = read(), y = read();
		ins(x, y), ins(y, x);
	} dfs(1);
	for(int i = 1; i <= n; i++) belong[i] = (i - 1) / m + 1;
	int tp1 = 0, tp2 = 0;
	for(int i = 1; i <= Q; i++) {
		int opt = read();
		if(opt == 0) {
			cg[++tp2].x = read();
			cg[tp2].y = read();
			if(cg[tp2].y > n) cg[tp2].y = n;
			cg[tp2].last = b[cg[tp2].x];
			b[cg[tp2].x] = cg[tp2].y;
		}
		else {
			q[++tp1].x = read(), q[tp1].y = read();
			q[tp1].last = tp2;
			q[tp1].id = tp1;
		}
	} sort(q + 1, q + tp1 + 1, cmp);
	m = sqrt(n);
	for(int i = 1; i <= n; i++) {
		belong[i] = (i - 1) / m + 1;
		if(belong[i] != belong[i - 1]) ll[belong[i]] = i, rr[belong[i - 1]] = i - 1;
	} belong[0] = 1; ll[1] = 0; rr[belong[n]] = n;
	ans = 0; int x = q[1].x, y = q[1].y, tt = q[1].last;
	for(int i = 1; i <= tt; i++) a[cg[i].x] = cg[i].y;
	int lca = LCA(x, y);
	solve(x, y); bak(lca);
	for(int i = 1; i <= belong[n]; i++) {
		if(kk[i] != rr[i] - ll[i] + 1) {
			for(int j = ll[i]; j <= rr[i]; j++) {
				if(s[j] == 0) {ans = j; break;}
			} break;
		}
	} bak(lca), A[q[1].id] = ans;
	for(int i = 2; i <= tp1; i++) {
		ct(tt, q[i].last); tt = q[i].last;
		solve(x, q[i].x), solve(y, q[i].y);
		x = q[i].x, y = q[i].y;
		int lca = LCA(x, y); bak(lca);
		for(int j = 1; j <= belong[n]; j++) {
			if(kk[j] != rr[j] - ll[j] + 1) {
				for(int k = ll[j]; k <= rr[j]; k++) {
					if(s[k] == 0) {ans = k; break;}
				} break;
			}
		} bak(lca), A[q[i].id] = ans;
	} for(int i = 1; i <= tp1; i++) printf("%d\n", A[i]);
	return 0;
}