【题目描述】
Description
给出一个n个节点的有根树(编号为0到n-1,根节点为0)。一个点的深度定义为这个节点到根的距离+1。
设dep[i]表示点i的深度,LCA(i,j)表示i与j的最近公共祖先。
有q次询问,每次询问给出l r z,求sigma_{l<=i<=r}dep[LCA(i,z)]。
(即,求在[l,r]区间内的每个节点i与z的最近公共祖先的深度之和)
Input
第一行2个整数n q。
接下来n-1行,分别表示点1到点n-1的父节点编号。
接下来q行,每行3个整数l r z。
Output
输出q行,每行表示一个询问的答案。每个答案对201314取模输出
Sample Input
Sample Output
HINT
共5组数据,n与q的规模分别为10000,20000,30000,40000,50000。
Source
【题解】
我们考虑这样一种暴力:
对于dep[lca(i,j)],可以将0~i路径上的点的权值+1,那么答案就是0~j路径上的点的权值之和。
因此对于[l,r]区间,可以将每个点到根节点的权值+1,那么答案ans[l,r]就是0~z路径上的点的权值之和。
显然ans[l,r]=ans[1,r]-ans[1,l-1]。
那么可以树链剖分,然后将0~n-1这n个点插入线段树中,顺便求出答案,复杂度O(nlogn^2)。
【Codes】
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int M=200010; const int mod=201314; int n,m,i,l,r,p,edgenum,Edgenum,time,x; int fa[M],head[M],vet[M],next[M],Head[M],Vet[M],Next[M],pre[M],clac[M],size[M],dep[M],son[M],tid[M],top[M],ans[M]; struct node{int l,r,sum,tag;}tree[M*4]; void addedge(int x,int y){ vet[++edgenum]=y; next[edgenum]=head[x]; head[x]=edgenum; } void Addedge(int x,int y,int z,int w){ Vet[++Edgenum]=y; Next[Edgenum]=Head[x]; Head[x]=Edgenum; pre[Edgenum]=z; clac[Edgenum]=w; } void dfs(int u,int d){ int e,v; int maxsize=0; size[u]=1,dep[u]=d; for (e=head[u];e;e=next[e]){ v=vet[e]; dfs(v,d+1); size[u]+=size[v]; if (size[v]>maxsize)maxsize=size[v],son[u]=v; } } void dfs1(int u,int ance){ int e,v; tid[u]=++time,top[u]=ance; if (son[u])dfs1(son[u],ance); for (e=head[u];e;e=next[e]){ v=vet[e]; if (v!=son[u])dfs1(v,v); } } void pushdown(int p){ tree[p<<1].tag+=tree[p].tag; tree[p<<1|1].tag+=tree[p].tag; tree[p].sum+=tree[p].tag*(tree[p].r-tree[p].l+1); tree[p].sum%=mod; tree[p].tag=0; } void pushup(int p){ pushdown(p<<1),pushdown(p<<1|1); tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum; tree[p].sum%=mod; } void build(int l,int r,int p){ tree[p].l=l,tree[p].r=r; if (l==r)return; int mid=l+r>>1; build(l,mid,p<<1); build(mid+1,r,p<<1|1); } int search(int x,int y,int l,int r,int p){ pushdown(p); if (x==l&&y==r)return tree[p].sum; int mid=l+r>>1; if (y<=mid)return search(x,y,l,mid,p<<1); else if (x>mid)return search(x,y,mid+1,r,p<<1|1); else return (search(x,mid,l,mid,p<<1)+search(mid+1,y,mid+1,r,p<<1|1))%mod; } void change(int x,int y,int l,int r,int p){ pushdown(p); if (x==l&&y==r){tree[p].tag+=1;return;} int mid=l+r>>1; if (y<=mid)change(x,y,l,mid,p<<1); else if (x>mid)change(x,y,mid+1,r,p<<1|1); else change(x,mid,l,mid,p<<1),change(mid+1,y,mid+1,r,p<<1|1); pushup(p); } void update(int u){ while (top[u]!=1)change(tid[top[u]],tid[u],1,n,1),u=fa[top[u]]; change(1,tid[u],1,n,1); } int query(int u){ int ans=0; while (top[u]!=1)ans+=search(tid[top[u]],tid[u],1,n,1),ans%=mod,u=fa[top[u]]; ans+=search(1,tid[u],1,n,1); ans%=mod; return ans; } int main(){ scanf("%d%d",&n,&m); for (i=1;i<n;i++){ scanf("%d",&x); fa[i+1]=x+1; addedge(x+1,i+1); } dfs(1,1); dfs1(1,1); build(1,n,1); for (i=1;i<=m;i++){ scanf("%d%d%d",&l,&r,&p); l++;r++;p++; Addedge(l-1,p,i,-1); Addedge(r,p,i,1); } for (i=1;i<=n;i++){ update(i); for (int e=Head[i];e;e=Next[e]){ int v=Vet[e]; ans[pre[e]]+=(mod+clac[e]*query(v))%mod; ans[pre[e]]%=mod; } } for (i=1;i<=m;i++)printf("%d\n",ans[i]); }