欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

BZOJ3626 [LNOI2014]LCA 树链剖分 线段树

程序员文章站 2022-05-27 14:37:48
...

欢迎访问~原文出处——博客园-zhouzhendong

去博客园看该题解


题目传送门 - BZOJ3626


题意概括

给出一个n个节点的有根树(编号为0到n-1,根节点为0)。一个点的深度定义为这个节点到根的距离+1。
设dep[i]表示点i的深度,LCA(i,j)表示i与j的最近公共祖先。
有q次询问,每次询问给出l r z,求在[l,r]区间内的每个节点i与z的最近公共祖先的深度之和


题解

http://hzwer.com/3891.html


 

代码

#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <vector>
using namespace std;
const int N=50005,mod=201314;
struct Gragh{
	int cnt,y[N*2],nxt[N*2],fst[N];
	void clear(){
		cnt=0;
		memset(fst,0,sizeof fst);
	}
	void add(int a,int b){
		y[++cnt]=b,nxt[cnt]=fst[a],fst[a]=cnt;
	}
}g;
int n,q,cnp=0,ans[N],L[N],R[N],wn[N];
int fa[N],son[N],depth[N],size[N],top[N],p[N],ap[N];
vector <int> bh[N];
struct Tree{
	int v,add,size;
}t[N*4];
void Get_Gen_Info(int rt,int pre,int d){
	depth[rt]=d,fa[rt]=pre,size[rt]=1,son[rt]=-1;
	for (int i=g.fst[rt];i;i=g.nxt[i])
		if (g.y[i]!=pre){
			int s=g.y[i];
			Get_Gen_Info(s,rt,d+1);
			size[rt]+=size[s];
			if (son[rt]==-1||size[s]>size[son[rt]])
				son[rt]=s;
		}
}
void Get_Top(int rt,int tp){
	top[rt]=tp;
	ap[p[rt]=++cnp]=rt;
	if (son[rt]==-1)
		return;
	Get_Top(son[rt],tp);
	for (int i=g.fst[rt];i;i=g.nxt[i]){
		int s=g.y[i];
		if (s!=fa[rt]&&s!=son[rt])
			Get_Top(s,s);
	}
}
void pushup(int rt){
	int ls=rt<<1,rs=ls|1;
	t[rt].v=t[ls].v+t[rs].v;
}
void build(int rt,int le,int ri){
	t[rt].add=t[rt].v=0,t[rt].size=ri-le+1;
	if (le==ri)
		return;
	int mid=(le+ri)>>1,ls=rt<<1,rs=ls|1;
	build(ls,le,mid);
	build(rs,mid+1,ri);
}
void pushdown(int rt){
	int ls=rt<<1,rs=ls|1,&a=t[rt].add;
	if (a){
		t[ls].add+=a,t[ls].v+=a*t[ls].size;
		t[rs].add+=a,t[rs].v+=a*t[rs].size;
		a=0;
	}
}
void update(int rt,int le,int ri,int xle,int xri,int v){
	if (xle>ri||xri<le)
		return;
	if (xle<=le&&ri<=xri){
		t[rt].v+=v*t[rt].size;
		t[rt].add+=v;
		return;
	}
	pushdown(rt);
	int mid=(le+ri)>>1,ls=rt<<1,rs=ls|1;
	update(ls,le,mid,xle,xri,v);
	update(rs,mid+1,ri,xle,xri,v);
	pushup(rt);
}
int query(int rt,int le,int ri,int xle,int xri){
	if (xle>ri||xri<le)
		return 0;
	if (xle<=le&&ri<=xri)
		return t[rt].v;
	pushdown(rt);
	int mid=(le+ri)>>1,ls=rt<<1,rs=ls|1;
	return query(ls,le,mid,xle,xri)+query(rs,mid+1,ri,xle,xri);
}
void Tupdate(int a){
	int f=top[a];
	while (a){
		update(1,1,n,p[f],p[a],1);
		a=fa[f],f=top[a];
	}
}
int Tquery(int a){
	int f=top[a],ans=0;
	while (a){
		ans+=query(1,1,n,p[f],p[a]);
		a=fa[f],f=top[a];
	}
	return ans;
}
int main(){
	scanf("%d%d",&n,&q);
	for (int i=1,a;i<n;i++){
		scanf("%d",&a);
		g.add(a+1,i+1);
		g.add(i+1,a+1);
	}
	Get_Gen_Info(1,0,0);
	Get_Top(1,1);
	build(1,1,n);
	for (int i=0;i<=n;i++)
		bh[i].clear();
	for (int i=1;i<=q;i++){
		scanf("%d%d%d",&L[i],&R[i],&wn[i]);
		L[i]++,R[i]++,wn[i]++;
		bh[L[i]-1].push_back(i);
		bh[R[i]].push_back(i);
	}
	memset(ans,0,sizeof ans);
	for (int i=1;i<=n;i++){
		Tupdate(i);
		for (int j=0;j<bh[i].size();j++){
			int k=bh[i][j];
			if (i==L[k]-1)
				ans[k]-=Tquery(wn[k]);
			else
				ans[k]+=Tquery(wn[k]);
		}
	}
	for (int i=1;i<=q;i++)
		printf("%d\n",ans[i]%mod);
	return 0;
}

  

转载于:https://www.cnblogs.com/zhouzhendong/p/BZOJ3626.html