[luoguP2146] 软件包管理器（树链剖分）

传送门

看着很吓人，其实就是个树链剖分模板。

可支持操作：

1.将节点 x 到 根 的路径上的值都变成 1

2.将以节点 x 为根的子树的值都变成 0

1A爽~

——代码

1 #include <cmath> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #define root 1, 1, n 6 #define ls now << 1, l, mid 7 #define rs now << 1 | 1, mid + 1, r 8 9 const int MAXN = 1000001; 10 int n, m, cnt, tim, ans; 11 int head[MAXN], to[MAXN], next[MAXN]; 12 int f[MAXN], son[MAXN], size[MAXN], deep[MAXN], tid[MAXN], top[MAXN], sum[MAXN << 2], turn[MAXN << 2]; 13 14 inline int read() 15 22 23 inline void add(int x, int y) 24 29 30 inline void dfs1(int u) 31 42 } 43 44 inline void dfs2(int u, int tp) 45 55 } 56 57 inline void swap(int &x, int &y) 58 61 62 inline void pushup(int now) 66 67 inline void pushdown(int now, int len) 68 76 77 inline void update(int x, int ql, int qr, int now, int l, int r) 78 86 if(r < ql || l > qr) return; 87 pushdown(now, r l + 1); 88 int mid = (l + r) >> 1; 89 update(x, ql, qr, ls); 90 update(x, ql, qr, rs); 91 pushup(now); 92 } 93 94 inline void qupdate(int x, int u, int v) 95 102 if(deep[u] > deep[v]) swap(u, v); 103 update(x, tid[u], tid[v], root); 104 } 105 106 int main() 107 120 dfs1(0); 121 dfs2(0, 0); 122 m = read(); 123 for(i = 1; i <= m; i++) 124 132 return 0; 133 }
View Code

上一篇：[codevs4655] 序列终结者（Splay）

下一篇：[luoguP1328] 生活大爆炸版石头剪刀布（模拟）

---

线段树 树链剖分