BZOJ3730 震波 <动态点分治>

Posted on Symbols count in article: 1.4k Reading time ≈ 5 mins.

Problem

震波

Time  Limit:  15  Sec\mathrm{Time\;Limit:\;15\;Sec}
Memory  Limit:  256  MB\mathrm{Memory\;Limit:\;256\;MB}

Description

在一片土地上有NN个城市，通过N−1N-1条无向边互相连接，形成一棵树的结构，相邻两个城市的距离为11，其中第i个城市的价值为valueivalue_i。
不幸的是，这片土地常常发生地震，并且随着时代的发展，城市的价值也往往会发生变动。
接下来你需要在线处理MM次操作：

  • 0  x  k0\;x\;k 表示发生了一次地震，震中城市为xx，影响范围为kk，所有与xx距离不超过kk的城市都将受到影响，该次地震造成的经济损失为所有受影响城市的价值和。
  • 1  x  y1\;x\;y 表示第xx个城市的价值变成了yy。

为了体现程序的在线性，操作中的x,y,kx,y,k都需要异或你程序上一次的输出来解密，如果之前没有输出，则默认上一次的输出为00。

Input

第一行包含两个正整数NN和MM。
第二行包含NN个正整数，第ii个数表示valueivalue_i。
接下来N−1N-1行，每行包含两个正整数u,vu,v，表示uu和vv之间有一条无向边。
接下来MM行，每行包含三个数，表示MM次操作。

Output

包含若干行，对于每个询问输出一行一个正整数表示答案。

Sample Input

1
2
3
4
5
6
7
8
9
10
8 1
1 10 100 1000 10000 100000 1000000 10000000
1 2
1 3
2 4
2 5
3 6
3 7
3 8
0 3 1

Sample Output

1
11100101

Hint

1≤N,M≤1051\le N,M\le10^5
1≤u,v,x≤N1\le u,v,x\le N
1≤valuei,y≤1041\le value_i,y\le10^4
0≤k≤N−10\le k\le N-1

标签：动态点分治

Solution

终于学会动态点分辣QAQ~
赶快来肝几道基础题

先不考虑时间复杂度，那么对于每个00操作显然可以暴力从震源向上爬统计答案。每次加上当前子树中距离符合题意的点，再减去其儿子（就是向上爬时此点的前驱）的子树中与其算重复的点。这样维护两个树状数组即可。
但是树高可以构造比log⁡n\log n大，这时就需要建立点分树，把树高降成log⁡n\log n。

提取重心建立点分树，对每个分治中心维护两个树状数组，第一个是其子树中到此分治中心的每种距离的所有点的点权和，第二个是其子树中到此分治中心的上一层分治中心的每种距离的所有点的点权和。
这样对于询问，每次log⁡n\log n向上爬，爬到每个分治中心log⁡size\log size统计；对于修改，每次log⁡n\log n向上爬，爬到每个分治中心log⁡size\log size更新树状数组即可。这样总复杂度是O(Qlog⁡2n)O(Q\log^2n)。

不过此题有些卡常，有三种策略：

  1. 用RMQ\mathrm{RMQ}做LCA\mathrm{LCA}
  2. 带fread大读优
  3. 将nn棵树状数组建到同一个大数组上，每个BIT\mathrm{BIT}记录其起始指针和终止指针，可以避免vector的一些常数

Code

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
#define LOG 16
#define MAX_N 100000
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, e, c[MAX_N+5], fa[MAX_N+5];
int w[MAX_N+5], sz[MAX_N+5], rt, tot;
int anc[MAX_N+5][LOG+1], dep[MAX_N+5];
int *p0[MAX_N+5], *p1[MAX_N+5], pr[MAX_N+5];
int BIT0[MAX_N*100], BIT1[MAX_N*100]; bool mrk[MAX_N+5];
struct node {int v, nxt;} E[(MAX_N<<1)+5];
void addedge(int u, int v) {E[e] = (node){v, pr[u]}, pr[u] = e++;}
void inc(int *tr, int p, int x, int l) {for (p = min(p+1, l); p <= l; p += (p&-p)) tr[p] += x;}
int sum(int *tr, int p, int l) {int ret = 0; for (p = min(p+1, l); p; p -= (p&-p)) ret += tr[p]; return ret;}
void init(int u) {
    for (int i = 1; i <= LOG; i++)
        anc[u][i] =anc[anc[u][i-1]][i-1];
    for (int i = pr[u], v; ~i; i = E[i].nxt)
        if ((v = E[i].v) ^ anc[u][0])
            anc[v][0] = u, dep[v] = dep[u]+1, init(v);
}
int LCA(int a, int b) {
    if (dep[a] < dep[b]) swap(a, b);
    for (int i = LOG; ~i; i--)
        if (dep[a]-(1<<i) >= dep[b]) a = anc[a][i];
    if (a == b) return a;
    for (int i = LOG; ~i; i--) if (anc[a][i]^anc[b][i])
        a = anc[a][i], b = anc[b][i];
    return anc[a][0];
}
int dist(int u, int v) {return dep[u]+dep[v]-2*dep[LCA(u, v)];}
int getsz(int u, int f) {
    int ret = 1;
    for (int i = pr[u], v; ~i; i = E[i].nxt)
        if (((v = E[i].v) ^ f) && !mrk[v])
            ret += getsz(v, u);
    return ret;
}
void getrt(int u, int f) {
    sz[u] = 1, w[u] = 0;
    for (int i = pr[u], v; ~i; i = E[i].nxt)
        if (((v = E[i].v) ^ f) && !mrk[v])
            getrt(v, u), sz[u] += sz[v], w[u] = max(w[u], sz[v]);
    w[u] = max(w[u], tot-sz[u]); if (w[u] < w[rt]) rt = u;
}
void divide(int u, int f) {
    rt = 0, tot = getsz(u, 0), getrt(u, 0);
    fa[u = rt] = f, mrk[u] = true, sz[u] = tot+1;
    for (int i = pr[u], v; ~i; i = E[i].nxt)
        if (!mrk[v = E[i].v]) divide(v, u);
}
void modify(int x, int y) {
    inc(p0[x], 0, y, sz[x]);
    for (int u = x; fa[u]; u = fa[u]) {
        int dis = dist(fa[u], x);
        inc(p1[u], dis, y, sz[u]);
        inc(p0[fa[u]], dis, y, sz[fa[u]]);
    }
}
int query(int x, int y) {
    int ret = sum(p0[x], y, sz[x]);
    for (int u = x, dis; fa[u]; u = fa[u]) if ((dis = dist(fa[u], x)) <= y)
        ret += sum(p0[fa[u]], y-dis, sz[fa[u]])-sum(p1[u], y-dis, sz[u]);
    return ret;
}
int main() {
    read(n), read(m), w[0] = n;
    memset(pr, -1, sizeof pr);
    for (int i = 1; i <= n; i++) read(c[i]);
    for (int i = 1, u, v; i < n; i++)
        read(u), read(v), addedge(u, v), addedge(v, u);
    init(1), divide(1, 0); int cnt = 0, lst = 0;
    for (int i = 1; i <= n; cnt += sz[i++]+1)
        p0[i] = BIT0+cnt, p1[i] = BIT1+cnt;
    for (int i = 1; i <= n; i++) modify(i, c[i]);
    while (m--) {
        int opt, x, y; read(opt);
        read(x), read(y), x ^= lst, y ^= lst;
        if (opt) modify(x, y-c[x]), c[x] = y;
        else printf("%d\n", lst = query(x, y));
    }
    return 0;
}