【題解】[bzoj3730]震波

在一片土地上有 $n$ 个城市,通过 $n-1$ 条无向边互相连接,形成一棵树的结构,相邻两个城市的距离为 $1$,其中第 $i$ 个城市的价值为 $value_i$。

不幸的是,这片土地常常发生地震,并且随着时代的发展,城市的价值也往往会发生变动。

接下来你需要在线处理 $m$ 次操作:

0 x k 表示发生了一次地震,震中城市为 $x$,影响范围为 $k$,所有与 $x$ 距离不超过 $k$ 的城市都将受到影响,该次地震造成的经济损失为所有受影响城市的价值和。

1 x y 表示第 $x$ 个城市的价值变成了 $y$ 。

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

這題有點自閉,各種 bug 調了好久。是點分樹沒錯,但是似乎不是很簡單,有一堆細節…

不過最後好像寫了個 $\log ^3$ ,死命卡常才給卡過去。

upd: 其實是大常數的 $\log ^2$ ,不知道我算複雜度的時候在瞎想什麼。

大概就是如果沒有修改操作的話,就是比較裸的點分樹。於是先考慮沒有修改操作的情況。

考慮怎麼維護這個東西,自然是希望對每個點都記錄一個桶,但這樣顯然由於每個點的深度不可控,最終需要的空間代價是 $O(n^2)$ 的。於是考慮怎麼調整樹的高度使得最終總的空間複雜度可以接受,那自然就會想到點分治。注意到點分治時,每個點在分治過程中,『邏輯樹高』都只有 $\log n$ 。這大概就是為什麼用點分樹的原因。

所以就是建出點分樹來,每個點維護一個 vector 作為桶,維護點分樹上子樹內到當前點距離為 $k$ 的點權和。這樣對於詢問,每次只需要跳點分樹,然後對於每個 $fa$ 統計 $k-dis(fa,x)$ 的點對的數量就好了。但是還有一個問題,就是對於以當前 $fa$ 為根的那些子樹,在算下一個 $fa$ 的時候會被算重。於是就要再維護一個桶,表示 $x$ 子樹內的點,到點分樹上 $x$ 的父親的距離為 $k$ 的點權和。由於邊權都為 $1$ ,這個操作就會很方便。

考慮如果帶修改,那無非就是把桶換成樹狀數組即可。這樣複雜度就會是 $O(m\log ^2 n)$ 的了。可能我寫的比較醜?預處理是常數不小的 $O(n\log ^2 n)$ ,似乎比其他人都慢誒…

然後是 bug 集錦:

1、最開始的時候維護的是 點分樹 上距離為 $k$ 的點的點權和。

2、然後改了改,但是查詢的時候沒有維護兩個 BIT,只維護了一個,然後減去的是查詢 $x$ 的點分樹子樹內到 $x$ 距離 $\leq k-2\times dis(fa_x,x)$ 的點權和。看上去有點東西,但問題在於到 $x$ 距離和到 $fa_x$ 距離沒有本質上的關係…比如可以在樹的對側。

3、最後還是寫了兩個 BIT,但是調了很久,原因是向上跳遇到 $dis(fa_x,x)>k$ 應該 continue 而不是 break ,因為這距離並是實際距離,在點分樹上沒有單調性。

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
#include <bits/stdc++.h>

using namespace std ;

#define il inline
#define to(k) E[k].to
#define next(k) E[k].next
#define low(x) (x & (-x))

const int N = 300010 ;

void debug(int *tp, int minn, int maxn, char c){
for (int i = minn ; i <= maxn ; ++ i)
cout << tp[i] << " " ; cout << c ;
}

int res ;
int ans ;
int lans ;
int n, m ;
int f[N] ;
int d[N] ;
int vis[N] ;
int dep[N] ;
int mx_dep ;
struct Edge{
int to ;
int next ;
}E[N * 2] ;
int cnt ;
int base[N] ;
int head[N] ;
unordered_map<int, int> Id[N] ;
vector <int> sub[N] ;
vector <int> buc[N] ;

il void add(int a, int b){
to(++ cnt) = b ;
next(cnt) = head[a] ;
head[a] = cnt ;
}
namespace findCG{
int grt ;
int num ;
int g[N] ;
int size[N] ;
il void chk(int &a, int b){
a = b <= a ? a : b ;
}
il void reset(){
g[grt = 0] = 19690126 ;
}
void dfs(int x, int fa){
size[x] = 1 ; g[x] = 0 ;
for (int k = head[x] ; k ; k = next(k)){
if (to(k) != fa && !vis[to(k)]){
dfs(to(k), x) ;
size[x] += size[to(k)] ;
g[x] = max(g[x], size[to(k)]) ;
}
}
chk(g[x], num - size[x]) ;
if (g[x] < g[grt]) grt = x ;
}
}
using namespace findCG ;

il void init(int root, int x){
for (int i = 0 ; i <= x ; ++ i)
buc[root].push_back(0) ;
}
il void add(int root, int x, int p){
int t = buc[root].size() ;
for ( ; x < t ; x += low(x)) buc[root][x] += p ;
}
il int ask(int root, int x){
int ret = 0 ;
if (x >= buc[root].size())
x = (int)buc[root].size() - 1 ;
for ( ; x ; x -= low(x)) ret += buc[root][x] ;
return ret ;
}
il void init2(int root, int x){
for (int i = 0 ; i <= x ; ++ i)
sub[root].push_back(0) ;
}
il void add2(int root, int x, int p){
int t = sub[root].size() ;
for ( ; x < t ; x += low(x)) sub[root][x] += p ;
}
il int ask2(int root, int x){
int ret = 0 ;
if (x >= sub[root].size())
x = (int)sub[root].size() - 1 ;
for ( ; x ; x -= low(x)) ret += sub[root][x] ;
return ret ;
}
void calc(int x, int fa, int root){
size[x] = 1 ;
dep[x] = dep[fa] + 1 ;
Id[root][x] = dep[x] ;
for (int i = head[x] ; i ; i = next(i))
if (!vis[to(i)] && to(i) != fa)
calc(to(i), x, root), size[x] += size[to(i)] ;
mx_dep = max(dep[x], mx_dep) ;
}
void calc2(int x, int fa, int root, int frt){
add(root, dep[x], base[x]) ;
if (frt) add2(root, Id[frt][x], base[x]) ;
for (int i = head[x] ; i ; i = next(i))
if (!vis[to(i)] && to(i) != fa) calc2(to(i), x, root, frt) ;
}
void find_tree(int x, int fa, int h){
int mx ; vis[x] = 1 ; mx_dep = 0 ;
calc(x, 0, x), init(x, mx_dep) ;
init2(x, h) ; mx = mx_dep ;
calc2(x, 0, x, fa) ;
for (int k = head[x] ; k ; k = next(k)){
if (vis[to(k)]) continue ;
num = size[to(k)] ; reset() ;
dfs(to(k), x) ; f[grt] = x ;
find_tree(grt, x, mx) ;
}
}
il int qr(){
int r = 0 ;
char c = getchar() ;
while (!isdigit(c)) c = getchar() ;
while (isdigit(c))
r = r * 10 + c - 48, c = getchar() ;
return r ;
}
int main(){
int a, b, c ; cin >> n >> m ;
for (int i = 1 ; i <= n ; ++ i) base[i] = qr() ;
for (int i = 1 ; i < n ; ++ i)
a = qr(), b = qr(), add(a, b), add(b, a) ;
reset() ; num = n ; dfs(1, 0) ; find_tree(grt, 0, 0) ;
while (m --){
a = qr() ;
b = qr() ^ lans ;
c = qr() ^ lans ;
if (!a){
int fb = f[b] ;
int ob, lb = b, df ;
ans += ask(lb, c + 1) ;
while (fb){
df = Id[fb][b] - 1 ;
if (c - df < 0){
lb = fb, fb = f[fb] ;
continue ;
}
ans += ask(fb, c - df + 1) ;
ans -= ask2(lb, c - df + 1) ;
lb = fb, fb = f[fb] ;
}
printf("%d", (lans = ans)) ;
ans = 0 ; putchar('\n') ;
}
else {
int ob = b ;
add(b, 1, -base[b] + c) ;
while (f[b]){
int df = Id[f[b]][ob] ;
add(f[b], df, -base[ob] + c) ;
add2(b, df, -base[ob] + c) ; b = f[b] ;
}
base[ob] = c ;
}
}
return 0 ;
}