题意：多次询问，每次求点的标号在[l, r]之间的所有点到点z的lca的深度。
解：看到这题有没有想到某一道很熟悉的题？紫妹和幽香是17岁的少女，喜欢可爱的东西......
显然这就是开店的超级无敌弱化版......直接套用做法就行了。
记得对"爱你一生一世"取模。(滑稽)
#include <cstdio>
#include <algorithm> typedef long long LL;
const int N = , M = ; struct Edge {
int nex, v;
}edge[N]; int tp; int e[N], top[N], num, fa[N], siz[N], son[N], d[N], n, pos[N];
LL sum[M];
int rt[N], tot, ls[M], rs[M], tag[M]; inline void adde(int x, int y) {
tp++;
edge[tp].v = y;
edge[tp].nex = e[x];
e[x] = tp;
return;
} void DFS1(int x) { // get siz fa son d
siz[x] = ;
d[x] = d[fa[x]] + ;
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
fa[y] = x;
DFS1(y);
siz[x] += siz[y];
if(siz[y] > siz[son[x]]) {
son[x] = y;
}
}
return;
} void DFS2(int x, int f) { // get pos id top
top[x] = f;
pos[x] = ++num;
if(son[x]) {
DFS2(son[x], f);
}
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(y == son[x]) {
continue;
}
DFS2(y, y);
}
return;
} void add(int x, int &y, int L, int R, int l, int r) {
if(!y || x == y) {
y = ++tot;
sum[y] = sum[x];
tag[y] = tag[x];
ls[y] = ls[x];
rs[y] = rs[x];
}
sum[y] += std::min(R, r) - std::max(L, l) + ;
if(L <= l && r <= R) {
tag[y]++;
return;
}
int mid = (l + r) >> ;
if(L <= mid) {
add(ls[x], ls[y], L, R, l, mid);
}
if(mid < R) {
add(rs[x], rs[y], L, R, mid + , r);
}
return;
} LL ask(int x, int y, int L, int R, int l, int r, int vx, int vy) {
if(L <= l && r <= R) {
return sum[y] - sum[x] + 1ll * (vy - vx) * (r - l + );
}
vx += tag[x];
vy += tag[y];
int mid = (l + r) >> ;
LL ans = ;
if(L <= mid) {
ans += ask(ls[x], ls[y], L, R, l, mid, vx, vy);
}
if(mid < R) {
ans += ask(rs[x], rs[y], L, R, mid + , r, vx, vy);
}
return ans;
} inline void add(int x, int time) {
while(x) {
add(rt[time - ], rt[time], pos[top[x]], pos[x], , n);
x = fa[top[x]];
}
return;
} inline LL ask(int x, int y, int z) {
LL ans = ;
while(z) {
ans += ask(rt[x - ], rt[y], pos[top[z]], pos[z], , n, , );
z = fa[top[z]];
}
return ans;
} int main() {
int q;
scanf("%d%d", &n, &q);
for(int i = , x; i <= n; i++) {
scanf("%d", &x);
adde(x + , i);
}
DFS1();
DFS2(, );
for(int i = ; i <= n; i++) {
add(i, i);
}
for(int i = , x, y, z; i <= q; i++) {
scanf("%d%d%d", &x, &y, &z);
LL t = ask(x + , y + , z + );
printf("%lld\n", t % );
}
return ;
}
AC代码