https://www.luogu.org/problemnew/show/P4211
baoli
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N = 5e4 + 10; const int Mod = 201314; #define gc getchar() #define RR freopen("gg.in", "r", stdin) int fa[N] = {-1}, deep[N], cnt[N], head[N]; struct Node {int u, v, nxt;} G[N]; int n, Ty, now = 1; inline int read() { int x = 0; char c = gc; while(c < '0' || c > '9') c = gc; while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc; return x; } inline void Add(int u, int v) { G[now].u = u; G[now].v = v; G[now].nxt = head[u]; head[u] = now ++; } void Dfs(int u, int dep) { deep[u] = dep; for(int i = head[u]; ~ i; i = G[i].nxt) { int v = G[i].v; if(v != fa[u]) Dfs(v, dep + 1); } } void Dfs_2(int u) { if(head[u] == -1) return ; for(int i = head[u]; ~ i; i = G[i].nxt) { int v = G[i].v; if(v != fa[u]) { Dfs_2(v); cnt[u] += cnt[v]; } } } int main() { n = read(); Ty = read(); for(int i = 0; i < n; i ++) head[i] = -1; for(int i = 1; i < n; i ++) { int u = read(); fa[i] = u; Add(u, i); Add(i, u); } Dfs(0, 1); while(Ty --) { int l = read(); int r = read(); int z = read(); for(int i = l; i <= r; i ++) cnt[i] ++; Dfs_2(0); int imp = z; int Answer = 0; while(fa[imp] != -1) { Answer += cnt[imp]; Answer %= Mod; imp = fa[imp]; } Answer += cnt[imp]; Answer %= Mod; cout << Answer << endl; memset(cnt, 0, sizeof cnt); } return 0; }
考虑这样的等价问题,如果我们把一个点 x 到 Root 的路径上每个点的权值赋为 1 ,其余点的权值为 0,那么从 LCA(x, y) 的 Depth 就是从 y 到 Root 的路径上的点权和。
这个方法是可以叠加的,这是非常有用的一点。如果我们把 [l, r] 的每个点到 Root 的路径上所有点的权值 +1,再求出从 c 到 Root 的路径点权和,即为 [l, r] 中所有点与 c 的 LCA 的 Depth 和。
不仅满足可加性,还满足可减性,这就更好了!
那么我们就可以对每个询问 [l, r] 做一个差分,用 Query(r) – Query(l – 1) 作为答案。这样就有一种离线算法:将 n 个点依次操作,将其到 Root 的路径上的点权值 +1 ,然后如果这个点是某个询问的 l – 1 或 r ,就用那个询问的 c 求一下到 Root 的路径和,算入答案中。
#include<cmath> #include<ctime> #include<queue> #include<stack> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define N 50005 #define M 201314 #define K 150005 using namespace std; struct graph { int nxt,to; } e[N]; struct quest { int x,z,n,ans; } l[N],r[N]; struct linetree { int l,r,s,len,lzy; } lt[K]; int g[N],n,q,t1,t2,cnt; int f[N],p[N],dep[N],top[N],siz[N],son[N]; inline int read() { int ret=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { ret=(ret<<1)+(ret<<3)+c-'0'; c=getchar(); } return ret; } inline void addedge(int x,int y) { e[++cnt].nxt=g[x]; g[x]=cnt; e[cnt].to=y; } inline void dfs1(int u) { int m=0; siz[u]=1; for(int i=g[u]; i; i=e[i].nxt) { f[e[i].to]=u; dep[e[i].to]=dep[u]+1; dfs1(e[i].to); siz[u]+=siz[e[i].to]; if(siz[e[i].to]>m) { son[u]=e[i].to; m=siz[e[i].to]; } } } inline void dfs2(int u,int tp) { top[u]=tp; p[u]=++cnt; if(son[u]) dfs2(son[u],tp); for(int i=g[u]; i; i=e[i].nxt) if(e[i].to!=son[u]) dfs2(e[i].to,e[i].to); } inline void build(int u,int l,int r) { lt[u].l=l; lt[u].r=r; lt[u].len=lt[u].r-lt[u].l+1; if(lt[u].l<lt[u].r) { int lef=u<<1,rig=u<<1|1; int mid=lt[u].l+lt[u].r>>1; build(lef,l,mid); build(rig,mid+1,r); } } inline int cover(int u,int l,int r) { if(lt[u].l>=l&<[u].r<=r) { ++lt[u].lzy; lt[u].s=(lt[u].s+lt[u].len)%M; } else if(lt[u].l<lt[u].r) { int lef=u<<1,rig=u<<1|1; int mid=lt[u].l+lt[u].r>>1; if(lt[u].lzy) { lt[lef].lzy+=lt[u].lzy; lt[rig].lzy+=lt[u].lzy; lt[lef].s=(lt[lef].s+lt[lef].len*lt[u].lzy)%M; lt[rig].s=(lt[rig].s+lt[rig].len*lt[u].lzy)%M; lt[u].lzy=0; } if(l<=mid) cover(lef,l,r); if(r>mid) cover(rig,l,r); lt[u].s=(lt[lef].s+lt[rig].s)%M; } } inline int ask(int u,int l,int r) { if(lt[u].l>=l&<[u].r<=r) return lt[u].s; if(lt[u].l<lt[u].r) { int lef=u<<1,rig=u<<1|1,ret=0; int mid=lt[u].l+lt[u].r>>1; if(lt[u].lzy) { lt[lef].lzy+=lt[u].lzy; lt[rig].lzy+=lt[u].lzy; lt[lef].s=(lt[lef].s+lt[lef].len*lt[u].lzy)%M; lt[rig].s=(lt[rig].s+lt[rig].len*lt[u].lzy)%M; lt[u].lzy=0; } if(l<=mid) ret=(ret+ask(lef,l,r))%M; if(r>mid) ret=(ret+ask(rig,l,r))%M; return ret; } } inline void add(int x,int y) { int t; while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]]) { t=x; x=y; y=t; } cover(1,p[top[x]],p[x]); x=f[top[x]]; } if(p[x]>p[y]) { t=x; x=y; y=t; } cover(1,p[x],p[y]); } inline int que(int x,int y) { int ret=0,t; while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]]) { t=x; x=y; y=t; } ret=(ret+ask(1,p[top[x]],p[x]))%M; x=f[top[x]]; } if(p[x]>p[y]) { t=x; x=y; y=t; } ret=(ret+ask(1,p[x],p[y]))%M; return ret; } inline bool cmp1(quest x,quest y) { return x.x<y.x; } inline bool cmp2(quest x,quest y) { return x.n<y.n; } inline void Aireen() { n=read(); q=read(); for(int i=2,j; i<=n; ++i) { j=read()+1; addedge(j,i); } for(int i=1; i<=q; ++i) { l[i].n=r[i].n=i; l[i].x=read(); r[i].x=read()+1; l[i].z=r[i].z=read()+1; } sort(l+1,l+1+q,cmp1); sort(r+1,r+1+q,cmp1); while(t1<=q&&!l[t1].x) ++t1; while(t2<=q&&!r[t2].x) ++t2; dep[1]=1; dfs1(1); cnt=0; dfs2(1,1); build(1,1,n); for(int i=1; i<=n; ++i) { add(1,i); while(t1<=q&&l[t1].x==i) { l[t1].ans=que(1,l[t1].z); ++t1; } while(t2<=q&&r[t2].x==i) { r[t2].ans=que(1,r[t2].z); ++t2; } } sort(l+1,l+1+q,cmp2); sort(r+1,r+1+q,cmp2); for(int i=1; i<=q; ++i) printf("%d ",(r[i].ans-l[i].ans+M)%M); } int main() { Aireen(); fclose(stdin); fclose(stdout); return 0; }