【题解】JZOJ6703 tree

题意

给定 $n$ 个点的树，每个点有点权，每次询问点权大于等于 $x$ 的点构成的子图有多少个连通块，动态修改点权，保证修改后点权不小于修改前。

题解

首先有一个显然的结论：森林的连通块个数 = 点数 - 边数。

这就是说，对于一个询问 $x$，我们只需要知道大于等于 $x$ 的点有多少个，所连两点均大于等于 $x$ 的边有多少条，就能算出答案。

考虑动态维护大于等于 $x$ 的点，发现这是一个单点修改区间查询，用一个统计后缀和的树状数组即可，每次修改就在原来的权值处减 $1$，在新的权值处加 $1$。查询 $[x,W_{max}]$ 的和即可。

考虑怎么维护边。同样用一个树状数组统计所连接两点大于等于 $x$ 的边。一条边的贡献显然是 $\min (a_u,a_v)$。

考虑 sub3，也就是菊花图。显然叶子节点的修改直接在树状数组上修改即可。对于根节点 $1$，开一个 multiset 维护大于等于 $a_1$ 的邻接点。对于 multiset 里面的点，其贡献显然是 $a_1$，其它的点贡献就是 $a_x$。时间复杂度 $O(n\log n)$。

考虑将这个做法拓展至每个点。每个点开 multiset $s_x$，存它的儿子里大于等于它的点。

对于一个修改 $a_x\leftarrow y$，考虑其儿子 $son$：

• $a_{son}<a_x$，$son$ 修改前后都不在 $s_x$ 中，边 $(x,son)$ 的贡献一直是 $a_{son}$
• $a_{son}\ge a_x,a_{son}<y$，$son$ 原本在 $s_x$ 中，修改后不在，边 $(x,son)$ 的贡献由 $a_x$ 变为 $a_{son}$
• $a_{son}\ge y$，$son$ 修改前后都在 $s_x$ 中，边 $(x,son)$ 的贡献由 $a_x$ 变为 $y$

考虑其父亲 $fa$：

• $y<a_{fa}$，$x$ 修改前后都不在 $s_{fa}$ 中，边 $(fa,x)$ 的贡献由 $a_x$ 变为 $y$
• $a_x<a_{fa},y\ge a_{fa}$，$x$ 修改前不在 $s_{fa}$ 中，修改后在 $s_{fa}$ 中，边 $(fa,x)$ 的贡献由 $a_x$ 变为 $a_{fa}$
• $a_x\ge a_{fa}$，$x$ 修改前后都在 $s_{fa}$ 中，边 $(fa,x)$ 的贡献一直是 $a_{fa}$

按照以上维护 $s_x$ 和树状数组即可。

容易发现，所有节点的 multiset 的大小总和一定是递减的。将一个点 $x$ 提升 $d$ 后，若想让 $x$ 再次加入 multiset，需要把 $[a_x,a_x+d]$ 的点全部修改才能做到。所以这个修改均摊 $O(1)$。总时间复杂度 $O(n\log n)$。

实现

这个树状数组的写法比较奇妙，是统计后缀和的。

注意不要漏了一些修改。

#include 
using namespace std;
#define fre(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
template<typename Ty> void read(Ty &x) {
	int c = getchar(), f = 1;
	for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
	for (x = 0; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
	x *= f;
}
#define lowbit(x) x & (-x)
const int N = 500005, W = 1000005;
int n, q, a[N], cnt = 0, fir[N], nxt[N << 1], to[N << 1], fa[N], tr[W], trp[W];
multiset<int> s[N];
void ade(int u, int v) {
	cnt++, nxt[cnt] = fir[u], fir[u] = cnt, to[cnt] = v;
	cnt++, nxt[cnt] = fir[v], fir[v] = cnt, to[cnt] = u;
}
void upd(int x, int val) { for (; x; x -= lowbit(x)) tr[x] += val; }
int gsum(int x) {
	int sum = 0;
	for (; x < W; x += lowbit(x)) sum += tr[x];
	return sum;
}
void updp(int x, int val) { for (; x; x -= lowbit(x)) trp[x] += val; }
int gsump(int x) {
	int sum = 0;
	for (; x < W; x += lowbit(x)) sum += trp[x];
	return sum;
}
void dfs(int r) {
	for (int i = fir[r]; i; i = nxt[i])
		if (to[i] != fa[r]) {
			fa[to[i]] = r, dfs(to[i]);
			if (a[to[i]] >= a[r]) s[r].insert(a[to[i]]);
			else upd(a[to[i]], 1);
		}
}
int main() {
	fre(tree);
	read(n), read(q);
	for (int i = 1; i <= n; i++) read(a[i]), updp(a[i], 1);
	for (int i = 1, u, v; i < n; i++) read(u), read(v), ade(u, v);
	dfs(1);
	for (int i = 1; i <= n; i++)
		if (!s[i].empty())
			upd(a[i], s[i].size());
	for (int t = 1, opt, x, y; t <= q; t++) {
		read(opt);
		if (opt == 1) {
			read(x), read(y);
			if (fa[x]) {
				if (a[x] >= a[fa[x]]) s[fa[x]].erase(s[fa[x]].find(a[x]));
				else upd(a[x], -1), upd(min(y, a[fa[x]]), 1);
				if (y >= a[fa[x]]) s[fa[x]].insert(y);
			}
			int cn = 0;
			while (!s[x].empty() && *s[x].begin() < y) upd(*s[x].begin(), 1), s[x].erase(s[x].begin()), cn++;
			upd(a[x], -cn), upd(a[x], -s[x].size()), upd(y, s[x].size()), updp(a[x], -1), updp(a[x] = y, 1);
		}
		else read(x), printf("%d\n", gsump(x) - gsum(x));
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63