BZOJ 3626: [LNOI2014]LCA(树剖+差分+线段树)

解题思路

　　比较有意思的一道题。首先要把求\(\sum\limits_{i=l}^r dep[lca(i,z)]\)这个公式变一下。就是考虑每一个点的贡献，做出贡献的点一定在\(z\)到根节点的路径上，对于\(x\)这个点，它的贡献就是区间\([l,r]\)与\(z\)的\(lca\)在它下方的个数。那么就可以将区间内的每一个点到根的路径权值都\(+1\)，然后求一下\(z\)到根节点的权值即为答案，这样的话用线段树就行了。但每次询问要暴力清空线段树，时间复杂度是\(O(qnlog^2n)\)的，承受不住。现在考虑怎样优化一下\(q\)，首先询问是可以拆成两端的，就是\([1,r]-[1,l-1]\)的形式，然后这样的话就不用暴力清空了。只需要离线预处理，把区间拆成两部分，按右端点排序(左端点都是\(1\))，然后每次修改时只需要修改当前询问到上一个询问这段区间就行了，修改时每个点最多只会被改一次。时间复杂度\(O(nlog^2n)\)

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<cstdlib>

#include<algorithm>

using namespace std;

const int MAXN = 50005;

const int MOD = 201314;

inline int rd(){

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}

	while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

	return f?x:-x;

}

int n,Q,head[MAXN],cnt,to[MAXN<<1],nxt[MAXN<<1],ans[MAXN];

int dep[MAXN],siz[MAXN],son[MAXN],fa[MAXN],top[MAXN],id[MAXN],num;

int sum[MAXN<<2],tag[MAXN<<2];

struct Query{

	int pos,type,id,z;

	friend bool operator<(const Query A,const Query B){

		return A.pos<B.pos;

	}

}q[MAXN<<1];

inline void add(int bg,int ed){

	to[++cnt]=ed,nxt[cnt]=head[bg],head[bg]=cnt;

}

void dfs1(int x,int f,int d){

	fa[x]=f;dep[x]=d;siz[x]=1;

	int maxson=-1,u;

	for(int i=head[x];i;i=nxt[i]){

		u=to[i];if(u==f) continue;

		dfs1(u,x,d+1);siz[x]+=siz[u];

		if(siz[u]>maxson) {maxson=siz[u];son[x]=u;}

	}

}

void dfs2(int x,int topf){

	id[x]=++num;top[x]=topf;if(!son[x]) return;

	dfs2(son[x],topf);int u;

	for(int i=head[x];i;i=nxt[i]){

		u=to[i];if(u==fa[x] || u==son[x]) continue;

		dfs2(u,u);

	}

}

inline void pushdown(int x,int ln,int rn){

	sum[x<<1]+=tag[x]*ln%MOD;sum[x<<1]%=MOD;

	sum[x<<1|1]+=tag[x]*rn%MOD;sum[x<<1|1]%=MOD;

	tag[x<<1]+=tag[x];tag[x<<1|1]+=tag[x];tag[x]=0;

}

void update(int x,int l,int r,int L,int R){

	if(L<=l && r<=R) {sum[x]+=r-l+1;sum[x]%=MOD;tag[x]++;return;}

	int mid=(l+r)>>1;if(tag[x]) pushdown(x,mid-l+1,r-mid);

	if(L<=mid) update(x<<1,l,mid,L,R);

	if(mid<R)  update(x<<1|1,mid+1,r,L,R);

	sum[x]=sum[x<<1]+sum[x<<1|1];sum[x]%=MOD;

}

int query(int x,int l,int r,int L,int R){

	if(L<=l && r<=R) return sum[x];

	int mid=(l+r)>>1,ret=0;if(tag[x]) pushdown(x,mid-l+1,r-mid);

	if(L<=mid) ret=(ret+query(x<<1,l,mid,L,R))%MOD;

	if(mid<R) ret=(ret+query(x<<1|1,mid+1,r,L,R))%MOD;

	return ret;

}

void updRange(int x){

	while(top[x]!=1){

		update(1,1,n,id[top[x]],id[x]);

		x=fa[top[x]];

	}

	update(1,1,n,1,id[x]);

}

int qRange(int x){

	int ret=0;

	while(top[x]!=1){

		ret=(ret+query(1,1,n,id[top[x]],id[x]))%MOD;

		x=fa[top[x]];

	}

	ret=(ret+query(1,1,n,1,id[x]))%MOD;

	return ret;

}

int main(){

	n=rd(),Q=rd();int x,y,z;

	for(int i=2;i<=n;i++){

		x=rd()+1;add(x,i);add(i,x);

	}

	dfs1(1,0,1);dfs2(1,1);

	for(int i=1;i<=Q;i++){

		x=rd(),y=rd(),z=rd();y++;z++;

		q[(i<<1)-1].id=i;q[(i<<1)-1].type=1;q[(i<<1)-1].pos=x;q[(i<<1)-1].z=z;

		q[i<<1].id=i;q[i<<1].type=2;q[i<<1].pos=y;q[i<<1].z=z;

	}

	sort(q+1,q+1+(Q<<1));

	for(int i=1;i<=(Q<<1);i++){

		if(!q[i].pos) continue;

		for(int j=q[i-1].pos+1;j<=q[i].pos;j++) updRange(j);

		if(q[i].type==2) ans[q[i].id]+=qRange(q[i].z);

		else ans[q[i].id]-=qRange(q[i].z);ans[q[i].id]%=MOD;

	}

	for(int i=1;i<=Q;i++)

		printf("%d\n",(ans[i]+MOD)%MOD);

	return 0;

}

巴特西

BZOJ 3626: [LNOI2014]LCA(树剖+差分+线段树)

解题思路

代码

最新文章

热门文章