q个询问
给出(l,r,z)
求 (sum_{i=l}^{r} dep[Lca(i,z)])
(n,q leq 5*10^4)
这显然是不太可做的 如果你要用 (nq log n) 的做法
考虑离线。
把询问拆成 [(1,l-1)] , [(1,r)]
求出来的结果自然是 [(1,r)] - [(1,l-1)]
没有固定的点？怎么办？
我们想。假设当前询问点是 z 选到 x 这个点 ((l leq x leq r))
那么 z 和 x 的 LCA 一定在 x 和 1 的路径上
所以每次 链上修改 把 x -> 1 的这条链整体加1
查询的时候 查询 1 ~ z 的链上的值就可以了。
至于链上整体加1 以及链上查询 可以用树链剖分+线段树解决。
如果没能理解 很抱歉我菜的可怜只能放一张比较特殊的图 让读者自行理解了。。
#include<bits/stdc++.h>
using namespace std ;
const int MAXN = 5e4 + 10 ;
struct Query { int z , flg , id ; } ;
vector < Query > v[MAXN] ;
int n , Q ;
struct Edge { int v , nxt ; } e[MAXN << 1] ;
int head[MAXN] , cnt = 0 ;
inline void add(int u , int v) { e[++ cnt] = {v , head[u]} ; head[u] = cnt ; }
typedef int arr[MAXN] ;
arr sz , fa , d , son ;
inline void dfs(int u) {
sz[u] = 1 ;
for(register int i = head[u] ; i ; i = e[i].nxt) {
int v = e[i].v ;
if(v == fa[u]) continue ;
fa[v] = u ;
d[v] = d[u] + 1 ;
dfs(v) ;
sz[u] += sz[v] ;
if(sz[v] > sz[son[u]]) son[u] = v ;
}
}
arr top , id , seq ; int idx = 0 ;
inline void dfs(int u , int t) {
top[u] = t ; id[u] = ++ idx ; seq[idx] = u ;
if(! son[u]) return ; dfs(son[u] , t) ;
for(register int i = head[u] ; i ; i = e[i].nxt) {
int v = e[i].v ;
if(v == fa[u] || v == son[u]) continue ;
dfs(v , v) ;
}
}
const int Mod = 201314 ;
int sum[MAXN << 2] , tag[MAXN << 2] ;
inline void pushup(int rt) {
sum[rt] = sum[rt << 1] + sum[rt << 1 | 1] ;
if(sum[rt] >= Mod) sum[rt] -= Mod ;
}
inline void build(int l , int r , int rt) {
if(l == r) { sum[rt] = tag[rt] = 0 ; return ; }
int mid = l + r >> 1 ;
build(l , mid , rt << 1) ;
build(mid + 1 , r , rt << 1 | 1) ;
pushup(rt) ;
}
inline void pushdown(int rt , int l , int r) {
if(! tag[rt]) return ;
tag[rt << 1] += tag[rt] ;
tag[rt << 1 | 1] += tag[rt] ;
int mid = l + r >> 1 ;
sum[rt << 1] += tag[rt] * (mid - l + 1) ;
sum[rt << 1 | 1] += tag[rt] * (r - mid) ;
tag[rt] = 0 ;
return ;
}
inline void update(int a , int b , int l , int r , int rt) {
if(a <= l && r <= b) { sum[rt] += r - l + 1 ; tag[rt] ++ ; return ; }
pushdown(rt , l , r) ;
int mid = l + r >> 1 ;
if(a <= mid) update(a , b , l , mid , rt << 1) ;
if(b > mid) update(a , b , mid + 1 , r , rt << 1 | 1) ;
pushup(rt) ;
}
inline int query(int a , int b , int l , int r , int rt) {
if(a <= l && r <= b) { return sum[rt] ; }
pushdown(rt , l , r) ;
int mid = l + r >> 1 , ans = 0 ;
if(a <= mid) ans += query(a , b , l , mid , rt << 1) ;
if(b > mid) ans += query(a , b , mid + 1 , r , rt << 1 | 1) ;
return ans ;
}
inline void upd_range(int x , int y) {
int fx = top[x] , fy = top[y] ;
while(fx ^ fy) {
if(d[fx] < d[fy]) swap(x , y) , swap(fx , fy) ;
update(id[fx] , id[x] , 1 , n , 1) ;
x = fa[fx] , fx = top[x] ;
}
if(d[x] > d[y]) swap(x , y) ;
update(id[x] , id[y] , 1 , n , 1) ;
}
inline int query_range(int x , int y) {
int fx = top[x] , fy = top[y] , ans = 0 ;
while(fx ^ fy) {
if(d[fx] < d[fy]) swap(x , y) , swap(fx , fy) ;
ans += query(id[fx] , id[x] , 1 , n , 1) ;
x = fa[fx] , fx = top[x] ;
}
if(d[x] > d[y]) swap(x , y) ;
return ans += query(id[x] , id[y] , 1 , n , 1) ;
}
int ans[MAXN] ;
signed main() {
#define _WIN64
freopen("0.in" , "r" , stdin) ;
#endif
ios_base :: sync_with_stdio(false) ;
cin.tie(nullptr) ;
cout.tie(nullptr) ;
cin >> n >> Q ;
for(int i = 2 ; i <= n ; i ++) { int fa ; cin >> fa ; add(i , ++ fa) ; add(fa , i) ; }
dfs(1) ; dfs(1 , 1) ; build(1 , n , 1) ;
for(int i = 1 ; i <= Q ; i ++) {
int l , r , z ;
cin >> l >> r >> z ; ++ l ; ++ r ; ++ z ;
v[l - 1].push_back({z , - 1 , i}) ; v[r].push_back({z , 1 , i}) ;
}
for(register int i = 1 ; i <= n ; i ++) {
upd_range(1 , i) ;
for( Query x : v[i] ) ans[x.id] = (ans[x.id] + x.flg * query_range(1 , x.z) + Mod) % Mod ;
}
for(register int i = 1 ; i <= Q ; i ++) cout << ans[i] << '
' ;
return 0 ;
}