三网合一网站远吗,亩地 wordpress,在线高清观看免费ppt,中国建设人才网证书查询题意
给定 n n n 个点的树#xff0c;每个点有点权#xff0c;每次询问点权大于等于 x x x 的点构成的子图有多少个连通块#xff0c;动态修改点权#xff0c;保证修改后点权不小于修改前。
题解
首先有一个显然的结论#xff1a;森林的连通块个数 点数 - 边数。
这…题意
给定 n n n 个点的树每个点有点权每次询问点权大于等于 x x x 的点构成的子图有多少个连通块动态修改点权保证修改后点权不小于修改前。
题解
首先有一个显然的结论森林的连通块个数 点数 - 边数。
这就是说对于一个询问 x x x我们只需要知道大于等于 x x x 的点有多少个所连两点均大于等于 x x x 的边有多少条就能算出答案。
考虑动态维护大于等于 x x x 的点发现这是一个单点修改区间查询用一个统计后缀和的树状数组即可每次修改就在原来的权值处减 1 1 1在新的权值处加 1 1 1。查询 [ x , W m a x ] [x,W_{max}] [x,Wmax] 的和即可。
考虑怎么维护边。同样用一个树状数组统计所连接两点大于等于 x x x 的边。一条边的贡献显然是 min ( a u , a v ) \min(a_u,a_v) min(au,av)。
考虑 sub3也就是菊花图。显然叶子节点的修改直接在树状数组上修改即可。对于根节点 1 1 1开一个 multiset 维护大于等于 a 1 a_1 a1 的邻接点。对于 multiset 里面的点其贡献显然是 a 1 a_1 a1其它的点贡献就是 a x a_x ax。时间复杂度 O ( n log n ) O(n\log n) O(nlogn)。
考虑将这个做法拓展至每个点。每个点开 multiset s x s_x sx存它的儿子里大于等于它的点。
对于一个修改 a x ← y a_x\larr y ax←y考虑其儿子 s o n son son a s o n a x a_{son}a_x asonax s o n son son 修改前后都不在 s x s_x sx 中边 ( x , s o n ) (x,son) (x,son) 的贡献一直是 a s o n a_{son} ason a s o n ≥ a x , a s o n y a_{son}\ge a_x,a_{son}y ason≥ax,asony s o n son son 原本在 s x s_x sx 中修改后不在边 ( x , s o n ) (x,son) (x,son) 的贡献由 a x a_x ax 变为 a s o n a_{son} ason a s o n ≥ y a_{son}\ge y ason≥y s o n son son 修改前后都在 s x s_x sx 中边 ( x , s o n ) (x,son) (x,son) 的贡献由 a x a_x ax 变为 y y y
考虑其父亲 f a fa fa y a f a ya_{fa} yafa x x x 修改前后都不在 s f a s_{fa} sfa 中边 ( f a , x ) (fa,x) (fa,x) 的贡献由 a x a_x ax 变为 y y y a x a f a , y ≥ a f a a_xa_{fa},y\ge a_{fa} axafa,y≥afa x x x 修改前不在 s f a s_{fa} sfa 中修改后在 s f a s_{fa} sfa 中边 ( f a , x ) (fa,x) (fa,x) 的贡献由 a x a_x ax 变为 a f a a_{fa} afa a x ≥ a f a a_x\ge a_{fa} ax≥afa x x x 修改前后都在 s f a s_{fa} sfa 中边 ( f a , x ) (fa,x) (fa,x) 的贡献一直是 a f a a_{fa} afa
按照以上维护 s x s_x sx 和树状数组即可。
容易发现所有节点的 multiset 的大小总和一定是递减的。将一个点 x x x 提升 d d d 后若想让 x x x 再次加入 multiset需要把 [ a x , a x d ] [a_x,a_xd] [ax,axd] 的点全部修改才能做到。所以这个修改均摊 O ( 1 ) O(1) O(1)。总时间复杂度 O ( n log n ) O(n\log n) O(nlogn)。
实现
这个树状数组的写法比较奇妙是统计后缀和的。
注意不要漏了一些修改。
#include bits/stdc.h
using namespace std;
#define fre(x) freopen(#x.in, r, stdin), freopen(#x.out, w, stdout)
templatetypename 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];
multisetint 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;
}
