可持久化点分树
简介
在一些神奇的问题中，光是维护点分树（动态点分治）是完全没有办法解决问题的，例如这道题，我们发现查询的区间是和树的形态无关的，这样的问题就不能单纯维护点分树，需要对点分树进行可持久化
算法流程
前置技能1.0 点分治
关于这个可以去看我上古时期的blog，如果这个都看不懂就直接退群吧。。。。
前置技能2.0 点分树（动态点分治）
听起来在点分治上加上了动态两个字，其实就是把点分治中分治中心用树型关系表示出来
在统计到一个点的信息的时候，我们就直接从这个点出发，往点分树父亲节点上跳，比如我们需要查询到u节点距离小于等k的点的个数，我们就先看当前分治中心u管辖区域内有多少个点和他的距离小于等于k，然后我们跳到prt[u]，查询在prt[u]的子树里面有多少个距离小于等于k - dis(prt[u], u)的节点，但是我们发现u的管辖区域内的点存在重复计算，所以我们需要把这一部分用相同的方法容斥掉，就可以计算答案了
修改和查询十分类似，不赘讲（江老著名梗）了
进入正题
可持久化点分树，就拿上面哪个cf题做例子吧，用问题作为切入点可能会好一些
首先我们可以发现这道题的查询是和树无关的，如果只有单点的查询是很快可以在点分树上处理出来的
并且我们知道查询是可以转化成前缀和查询的，于是就有了维护可持久化点分树的思路
因为平常的点分我们是从下到上更新，这次需要变成从上到下的插入，并且在点分树上添加出来一条新的链，所以在考虑继承上一个点分树的状态的时候，我们需要在插入的时候继承不改变的子树的信息，因此我们需要先将原来的树进行三度化处理，这样每个分治重心的儿子最多只有三个，就可以处理了
三度化的技巧主要在于理解左兄弟右儿子的思路，把所有的兄弟用长度为0的边串起来，这样在新的树上的距离就是在原树上的距离了，并且因为串两个兄弟只需要1个点，所以新的树的总点数也是$O(n)$级别的，不影响复杂度
具体代码实现长成这样：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
28void rebuild(int u, int fa) {
int last = 0, tmp = 0;
for (auto cur : edge[u]) {
int v = cur.first, w = cur.second;
if (v == fa) continue;
++tmp;
if (tmp == 1) {
addedge(u, v, w);
addedge(v, u, w);
last = u;
} else if (tmp == ((signed) edge[u].size()) - (u != 1)) {
addedge(last, v, w);
addedge(v, last, w);
} else {
m++;
addedge(last, m, 0);
addedge(m, last, 0);
last = m;
addedge(m, v, w);
addedge(v, m, w);
}
}
for (auto cur : edge[u]) {
int v = cur.first;
if (v == fa) continue;
rebuild(v, u);
}
}
其中edge是原树的边，addedge是新树的边
然后因为我们需要在点分树上更新一直到节点u（当前的更新节点）
所以我们需要记录一下在点分树上u的每个祖先v是prt[v]的哪一个儿子
这个可以在第一次点分树预处理出来
然后为了保证复杂度（不要多一个log）
最好用$O(n\log n)$预处理，$O(1)$查询的LCA
就是在欧拉序上进行处理
1 | namespace LCA { |
然后我们考虑普通的点分树在维护什么东西
首先是用来记录信息的值和用来进行容斥的值，因为这道题只需要记录距离，所以我们用两个值来表示就可以了，如果需要更复杂的维护就需要用到高级的数据结构了
我们查询到一个点的距离和的时候首先从根往下走，假设当前节点是v，查询节点是u，那么v除了u所在子树的所有点到u的所有距离就是除了u子树所有节点到v的距离和加上除了u所有子树的大小乘上u到v的距离
于是我们就可以进行容斥了
点分树部分的代码是这样的：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
namespace Tree_Devide {
struct Node {
int ch[3], id, siz;
ll sum[2];
} s[N * LOG];
int siz[N], F[N], dep[N], siz_all, rt, cnt = 0;
int root[N];
bool vis[N];
vector<int> pre[N];
void getroot(int u, int fa) {
siz[u] = 1;
F[u] = 0;
for (int i = head[u]; i; i = E[i].nxt) {
int v = E[i].v;
if (v == fa || vis[v]) continue;
getroot(v, u);
siz[u] += siz[v];
F[u] = max(F[u], siz[v]);
}
F[u] = max(F[u], siz_all - siz[u]);
if (F[u] < F[rt]) rt = u;
}
void devide(int u) {
vis[u] = 1;
s[u].id = u;
for (int i = head[u]; i; i = E[i].nxt) {
int v = E[i].v;
if (vis[v]) continue;
F[rt = 0] = siz_all = siz[v];
getroot(v, 0);
dep[rt] = dep[u] + 1;
for (int j : pre[u]) {
pre[rt].push_back(j);
}
for (int j = 0; j < 3; j++) {
if (s[u].ch[j]) continue;
s[u].ch[j] = rt;
pre[rt].push_back(j);
devide(rt);
break;
}
}
}
void insert(int &t, int las, int u, int fa) {
t = ++cnt;
s[t] = s[las];
s[t].siz++;
s[t].sum[0] += getdis(s[t].id, u);
if (fa) {
s[t].sum[1] += getdis(s[fa].id, u);
}
if (s[t].id == u) return;
insert(s[t].ch[pre[u][dep[s[t].id]]], s[las].ch[pre[u][dep[s[t].id]]], u, t);
}
ll query(int t, int u) {
ll res = 0;
for (int i = 0; i < dep[u]; i++) {
int cur = s[t].ch[pre[u][i]];
res += (s[t].siz - s[cur].siz) * getdis(s[t].id, u) + s[t].sum[0] - s[cur].sum[1];
t = cur;
}
res += s[t].sum[0];
return res;
}
void build() {
F[rt = 0] = siz_all = cnt = m;
getroot(1, 0);
root[0] = rt;
devide(rt);
for (int i = 1; i <= n; i++) {
insert(root[i], root[i - 1], a[i], 0);
}
}
}
然后放一下cf757g的完整代码：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
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
const int N = 4e5 + 10;
const int LOG = 20;
struct Edge {
int v, w, nxt;
} E[N << 1];
int head[N], tot = 0;
int n, m, q, a[N];
vector<pi> edge[N];
void addedge(int u, int v, int w) {
E[++tot] = (Edge) {v, w, head[u]};
head[u] = tot;
}
void rebuild(int u, int fa) {
int last = 0, tmp = 0;
for (auto cur : edge[u]) {
int v = cur.first, w = cur.second;
if (v == fa) continue;
++tmp;
if (tmp == 1) {
addedge(u, v, w);
addedge(v, u, w);
last = u;
} else if (tmp == ((signed) edge[u].size()) - (u != 1)) {
addedge(last, v, w);
addedge(v, last, w);
} else {
m++;
addedge(last, m, 0);
addedge(m, last, 0);
last = m;
addedge(m, v, w);
addedge(v, m, w);
}
}
for (auto cur : edge[u]) {
int v = cur.first;
if (v == fa) continue;
rebuild(v, u);
}
}
namespace LCA {
int dep[N], st[N << 1][LOG], dfn[N], Log[N << 1], ind = 0;
ll dis[N];
void dfs(int u, int fa) {
st[dfn[u] = ++ind][0] = u;
for (int i = head[u]; i; i = E[i].nxt) {
int v = E[i].v;
if (v == fa) continue;
dep[v] = dep[u] + 1;
dis[v] = dis[u] + E[i].w;
dfs(v, u);
st[++ind][0] = u;
}
}
int checkmin(int x, int y) {
return dep[x] < dep[y] ? x : y;
}
void ST() {
dfs(1, 0);
for (int i = 2; i <= ind; i++) {
Log[i] = Log[i >> 1] + 1;
}
for (int j = 1; j < LOG; j++) {
for (int i = 1; i + (1 << j) - 1 <= ind; i++) {
st[i][j] = checkmin(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
}
}
int lca(int x, int y) {
x = dfn[x], y = dfn[y];
if (x > y) swap(x, y);
int k = Log[y - x + 1];
return checkmin(st[x][k], st[y - (1 << k) + 1][k]);
}
ll getdis(int x, int y) {
return dis[x] + dis[y] - dis[lca(x, y)] * 2;
}
}
using LCA::getdis;
namespace Tree_Devide {
struct Node {
int ch[3], id, siz;
ll sum[2];
} s[N * LOG];
int siz[N], F[N], dep[N], siz_all, rt, cnt = 0;
int root[N];
bool vis[N];
vector<int> pre[N];
void getroot(int u, int fa) {
siz[u] = 1;
F[u] = 0;
for (int i = head[u]; i; i = E[i].nxt) {
int v = E[i].v;
if (v == fa || vis[v]) continue;
getroot(v, u);
siz[u] += siz[v];
F[u] = max(F[u], siz[v]);
}
F[u] = max(F[u], siz_all - siz[u]);
if (F[u] < F[rt]) rt = u;
}
void devide(int u) {
vis[u] = 1;
s[u].id = u;
for (int i = head[u]; i; i = E[i].nxt) {
int v = E[i].v;
if (vis[v]) continue;
F[rt = 0] = siz_all = siz[v];
getroot(v, 0);
dep[rt] = dep[u] + 1;
for (int j : pre[u]) {
pre[rt].push_back(j);
}
for (int j = 0; j < 3; j++) {
if (s[u].ch[j]) continue;
s[u].ch[j] = rt;
pre[rt].push_back(j);
devide(rt);
break;
}
}
}
void insert(int &t, int las, int u, int fa) {
t = ++cnt;
s[t] = s[las];
s[t].siz++;
s[t].sum[0] += getdis(s[t].id, u);
if (fa) {
s[t].sum[1] += getdis(s[fa].id, u);
}
if (s[t].id == u) return;
insert(s[t].ch[pre[u][dep[s[t].id]]], s[las].ch[pre[u][dep[s[t].id]]], u, t);
}
ll query(int t, int u) {
ll res = 0;
for (int i = 0; i < dep[u]; i++) {
int cur = s[t].ch[pre[u][i]];
res += (s[t].siz - s[cur].siz) * getdis(s[t].id, u) + s[t].sum[0] - s[cur].sum[1];
t = cur;
}
res += s[t].sum[0];
return res;
}
void build() {
F[rt = 0] = siz_all = cnt = m;
getroot(1, 0);
root[0] = rt;
devide(rt);
for (int i = 1; i <= n; i++) {
insert(root[i], root[i - 1], a[i], 0);
}
}
}
using Tree_Devide::root;
using Tree_Devide::build;
using Tree_Devide::insert;
using Tree_Devide::query;
int main() {
scanf("%d %d", &n, &q);
m = n;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
for (int i = 1; i < n; i++) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
edge[u].push_back(make_pair(v, w));
edge[v].push_back(make_pair(u, w));
}
rebuild(1, 0);
LCA::ST();
build();
ll lastans = 0;
while (q--) {
int op, l, r, u;
scanf("%d", &op);
if (op == 1) {
scanf("%d %d %d", &l, &r, &u);
l ^= lastans;
r ^= lastans;
u ^= lastans;
lastans = query(root[r], u) - query(root[l - 1], u);
printf("%lld\n", lastans);
lastans %= (1 << 30);
} else {
scanf("%d", &u);
u ^= lastans;
swap(a[u], a[u + 1]);
insert(root[u], root[u - 1], a[u], 0);
}
}
return 0;
}