想在b站搜query on a tree系列不小心看到了这题
扑鼻而来的浓浓的OI风格的题面，6个操作，放在ACM界读完题就可以喷了(误
看到前三个操作...kdtree板子题，一维dfs序，一维dep，限制区间显然
后面三个操作...考虑树链剖分，这样点到根的路径就是几条不连续的链了
就把前面kdtree的一维dfs序换成树链剖分的方法得到的dfs序就行了
对于后面三个操作相当于把常写的树链剖分套线段树的线段树换成kdtree了
复杂度O(n*sqrt(n)*logn)，这样的话为什么后面三个操作不直接对树上路径进行操作呢...
写这个题...单纯为了一时爽...尤其是过了样例一发入魂的那种 feel...
1 #include2 3 using namespace std; 4 5 typedef long long ll; 6 7 const int N = 1e5 + 5; 8 9 int n, m, tot, head[N]; 10 11 int fa[N], siz[N], dep[N]; 12 13 int cnt, son[N], top[N], dfn[N], st[N], en[N]; 14 15 int nowD, lx, ly, rx, ry, val; 16 17 ll ans; 18 19 struct edge{ int to, next;}e[N]; 20 21 struct node { 22 ll siz, val, sum, lazy1, lazy2; 23 int maxd[2], mind[2], d[2]; 24 node *c[2]; 25 26 node() { 27 val = sum = siz = 0, lazy1 = 0, lazy2 = -1; 28 c[0] = c[1] = NULL; 29 } 30 31 void update(); 32 33 void pushup(); 34 35 void pushdown(); 36 37 bool operator < (const node &a) const { 38 return d[nowD] < a.d[nowD]; 39 } 40 }nodes[N]; 41 42 node *null = new node; 43 44 node *root; 45 46 inline void node::update() { 47 if (c[0] != null) { 48 if (c[0] -> maxd[0] > maxd[0]) maxd[0] = c[0] -> maxd[0]; 49 if (c[0] -> maxd[1] > maxd[1]) maxd[1] = c[0] -> maxd[1]; 50 if (c[0] -> mind[0] < mind[0]) mind[0] = c[0] -> mind[0]; 51 if (c[0] -> mind[1] < mind[1]) mind[1] = c[0] -> mind[1]; 52 } 53 if (c[1] != null) { 54 if (c[1] -> maxd[0] > maxd[0]) maxd[0] = c[1] -> maxd[0]; 55 if (c[1] -> maxd[1] > maxd[1]) maxd[1] = c[1] -> maxd[1]; 56 if (c[1] -> mind[0] < mind[0]) mind[0] = c[1] -> mind[0]; 57 if (c[1] -> mind[1] < mind[1]) mind[1] = c[1] -> mind[1]; 58 } 59 siz = 1 + c[0] -> siz + c[1] -> siz; 60 } 61 62 inline void node::pushup() { 63 sum = val + c[0] -> sum + c[1] -> sum; 64 } 65 66 inline void node::pushdown() { 67 if (lazy1 == 0 && lazy2 == -1) return; 68 if (lazy1 != 0) { 69 if (c[0] != null) { 70 c[0] -> val += lazy1; 71 c[0] -> sum += c[0] -> siz * lazy1; 72 if (c[0] -> lazy2 != -1) c[0] -> lazy2 += lazy1; 73 else c[0] -> lazy1 += lazy1; 74 } 75 if (c[1] != null) { 76 c[1] -> val += lazy1; 77 c[1] -> sum += c[1] -> siz * lazy1; 78 if (c[1] -> lazy2 != -1) c[1] -> lazy2 += lazy1; 79 else c[1] -> lazy1 += lazy1; 80 } 81 lazy1 = 0; 82 return; 83 } 84 if (lazy2 != -1) { 85 if (c[0] != null) { 86 c[0] -> val = lazy2; 87 c[0] -> sum = c[0] -> siz * lazy2; 88 c[0] -> lazy1 = 0; 89 c[0] -> lazy2 = lazy2; 90 } 91 if (c[1] != null) { 92 c[1] -> val = lazy2; 93 c[1] -> sum = c[1] -> siz * lazy2; 94 c[1] -> lazy1 = 0; 95 c[1] -> lazy2 = lazy2; 96 } 97 lazy2 = -1; 98 return; 99 }100 }101 102 inline void dfs1(int u) {103 siz[u] = 1;104 for (int v, i = head[u]; i; i = e[i].next) {105 v = e[i].to, fa[v] = u;106 dep[v] = dep[u] + 1;107 dfs1(v), siz[u] += siz[v];108 if (siz[v] > siz[son[u]]) son[u] = v;109 }110 }111 112 inline void dfs2(int u, int tp) {113 dfn[++ cnt] = u, st[u] = cnt, top[u] = tp;114 if (son[u]) dfs2(son[u], tp);115 for (int v, i = head[u]; i; i = e[i].next) {116 v = e[i].to;117 if (v != son[u]) dfs2(v, v);118 }119 en[u] = cnt;120 }121 122 inline node *build(int l, int r, int D) {123 int mid = l + r >> 1; nowD = D;124 nth_element(nodes + l, nodes + mid, nodes + r);125 node *res = &nodes[mid];126 if (l != mid) res -> c[0] = build(l, mid - 1, !D);127 else res -> c[0] = null;128 if (r != mid) res -> c[1] = build(mid + 1, r, !D);129 else res -> c[1] = null;130 res -> update();131 return res; 132 }133 134 inline void query1(node *o) {135 if (o == null) return;136 if (lx > o -> maxd[0] || ly > o -> maxd[1] || rx < o -> mind[0] || ry < o -> mind[1])137 return;138 if (lx <= o -> mind[0] && ly <= o -> mind[1] && rx >= o -> maxd[0]&& ry >= o -> maxd[1]) {139 ans += o -> sum; 140 return;141 }142 if (lx <= o -> d[0] && rx >= o -> d[0] && ly <= o -> d[1] && ry >= o -> d[1])143 ans += o -> val;144 o -> pushdown();145 query1(o -> c[0]), query1(o -> c[1]);146 }147 148 inline void modify2(node *o) {149 if (o == null) return;150 if (lx > o -> maxd[0] || ly > o -> maxd[1] || rx < o -> mind[0] || ry < o -> mind[1])151 return;152 if (lx <= o -> mind[0] && ly <= o -> mind[1] && rx >= o -> maxd[0] && ry >= o -> maxd[1]) {153 if (o -> lazy2 != -1) o -> lazy2 += val;154 else o -> lazy1 += val;155 o -> sum += o -> siz * val;156 o -> val += val;157 return;158 }159 if (lx <= o -> d[0] && rx >= o -> d[0] && ly <= o -> d[1] && ry >= o -> d[1])160 o -> val += val;161 o -> pushdown();162 modify2(o -> c[0]), modify2(o -> c[1]);163 o -> pushup();164 }165 166 inline void modify3(node *o) {167 if (o == null) return;168 if (lx > o -> maxd[0] || ly > o -> maxd[1] || rx < o -> mind[0] || ry < o -> mind[1])169 return;170 if (lx <= o -> mind[0] && ly <= o -> mind[1] && rx >= o -> maxd[0] && ry >= o -> maxd[1]) {171 o -> lazy1 = 0, o -> lazy2 = val;172 o -> val = val, o -> sum = o -> siz * val;173 return;174 }175 if (lx <= o -> d[0] && rx >= o -> d[0] && ly <= o -> d[1] && ry >= o -> d[1])176 o -> val = val;177 o -> pushdown();178 modify3(o -> c[0]), modify3(o -> c[1]);179 o -> pushup();180 }181 182 inline void ask4(node *o) {183 if (o == null) return;184 if (lx > o -> maxd[0] || rx < o -> mind[0]) return;185 if (lx <= o -> mind[0] && rx >= o -> maxd[0]) {186 ans += o -> sum; 187 return;188 }189 if (lx <= o -> d[0] && rx >= o -> d[0]) ans += o -> val;190 o -> pushdown();191 ask4(o -> c[0]), ask4(o -> c[1]);192 }193 194 inline void query4(int u) {195 for (int fu = top[u]; fu != 1; fu = top[u = fa[fu]])196 lx = st[fu], rx = st[u], ask4(root);197 lx = 1, rx = st[u], ask4(root);198 }199 200 inline void change5(node *o) {201 if (o == null) return;202 if (lx > o -> maxd[0] || rx < o -> mind[0])203 return;204 if (lx <= o -> mind[0] && rx >= o -> maxd[0]) {205 if (o -> lazy2 != -1) o -> lazy2 += val;206 else o -> lazy1 += val;207 o -> sum += o -> siz * val;208 o -> val += val;209 return;210 }211 if (lx <= o -> d[0] && rx >= o -> d[0])212 o -> val += val;213 o -> pushdown();214 change5(o -> c[0]), change5(o -> c[1]);215 o -> pushup();216 }217 218 inline void change6(node *o) {219 if (o == null) return;220 if (lx > o -> maxd[0] || rx < o -> mind[0]) return;221 if (lx <= o -> mind[0] && rx >= o -> maxd[0]) {222 o -> lazy1 = 0, o -> lazy2 = val;223 o -> val = val, o -> sum = o -> siz * val;224 return;225 }226 if (lx <= o -> d[0] && rx >= o -> d[0])227 o -> val = val;228 o -> pushdown();229 change6(o -> c[0]), change6(o -> c[1]);230 o -> pushup();231 }232 233 inline void modify5(int u) {234 for (int fu = top[u]; fu != 1; fu = top[u = fa[fu]])235 lx = st[fu], rx = st[u], change5(root);236 lx = 1, rx = st[u], change5(root);237 }238 239 inline void modify6(int u) {240 for (int fu = top[u]; fu != 1; fu = top[u = fa[fu]])241 lx = st[fu], rx = st[u], change6(root);242 lx = 1, rx = st[u], change6(root);243 }244 245 int main() {246 ios::sync_with_stdio(false);247 int testCase, op, u, l, r; 248 cin >> testCase >> n;249 for (int j, i = 2; i <= n; i ++)250 cin >> j, e[++ tot] = {i, head[j]}, head[j] = tot;251 dfs1(1), dfs2(1, 1);252 for (int i = 1; i <= n; i ++) {253 nodes[i].d[0] = nodes[i].maxd[0] = nodes[i].mind[0] = i;254 nodes[i].d[1] = nodes[i].maxd[1] = nodes[i].mind[1] = dep[dfn[i]];255 nodes[i].val = nodes[i].sum = 0, nodes[i].lazy1 = 0, nodes[i].lazy2 = -1;256 }257 root = build(1, n, 0);258 for (cin >> m; m --; ) {259 cin >> op;260 switch(op) {261 case 1:262 cin >> u >> l >> r;263 lx = st[u], ly = dep[u] + l;264 rx = en[u], ry = dep[u] + r;265 ans = 0, query1(root), cout << ans << endl;266 break;267 case 2:268 cin >> u >> l >> r >> val;269 lx = st[u], ly = dep[u] + l;270 rx = en[u], ry = dep[u] + r;271 modify2(root);272 break;273 case 3:274 cin >> u >> l >> r >> val;275 lx = st[u], ly = dep[u] + l;276 rx = en[u], ry = dep[u] + r;277 modify3(root);278 break;279 case 4:280 cin >> u, ans = 0;281 query4(u), cout << ans << endl;282 break;283 case 5:284 cin >> u >> val;285 modify5(u);286 break;287 case 6:288 cin >> u >> val;289 modify6(u);290 break;291 }292 }293 return 0;294 }
代码细节:
kdtree指针跑的比数组快，在数组比较大的时候速度差距比较明显
kdtree的这个update写法是固定的，必须要判左右儿子非null才更新，(后续更新需要调用update的情况下)常数大概是一倍
update其实是可以和pushup合并为用同一个函数的，但考虑后续修改只修改值不修改每个点的二维坐标，所以我分开了(1s的差距)
change5和change6是可以被modify2和modify3替代的，当然这时候要在modify5和modify6里对ly和ry两个变量也做调整