【题目描述】
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
5 2
0
0
1
1
1 4 3
1 4 2
Sample Output
8
5
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]);
}
评论 (0)
