[LNOI2014]LCA(树链剖分)

题意

给定n个节点的有根树,q次询问,每次询问求$sum _{lleq ileq r} dep[LCA(i,z)] $

思路

根据wys巨神所说,如果不把dep这个约束去掉,那么将不容易用数据结构来维护,因为对于不同的i,(dep[LCA])可能不一样

1.为了去掉dep,我们采取一种奇技淫巧,对于上面的一个 (i) ,将 (root)(i) 这条路径上的所有点权加一,那么(dep[LCA])就可以通过查询(root)(z)这条路径上的点权和得到(WTF???

于是问题变成了链修改链查询,可以请出我们代码简短好写的树链剖分同学

然而我们不能对每个询问都暴力修改(root)([l,r])这一些链,所以我们还需要一些小优化

2.离线处理,将每个询问拆成([1,l-1])([1,r])两份,那么这个询问可以用(ans[1,r]-ans[1,l-1])得到,由于链修改操作与z无关(因为增加(root)(i)所以只与(i)有关),所以可以对所有询问的右端点排序,然后for一遍依次链修改即可

树链剖分模板题,据说可以在线做可是我太蒻了不会啊

由于有很多重复的操作(+代码过丑)所以去掉不必要的部分啦~~~

Code:

struct Q
{
	int r,z,opt;
	ll ans;
	bool operator < (const Q a)const
	{
		return r<a.r;
	}
}q[N<<1];int qsum=-1;
bool cmp(Q a,Q b) {return a.opt<b.opt;}
int main()
{
	read(n);read(m);
	for(int i=1;i<n;++i)
	{
		int father; read(father);
		add_edge(father+1,i+1);
	}
	for(int i=1;i<=m;++i)
	{
		int l,r,z;
		read(l);read(r);read(z);
		++l;++r;++z;
		q[++qsum].r=l-1; q[qsum].z=z; q[qsum].opt=qsum;
		q[++qsum].r=r; q[qsum].z=z; q[qsum].opt=qsum;
	}
	sort(q,q+qsum+1);
	seg[1]=rev[1]=top[1]=hfu=1;
	dfs1(1);
	dfs2(1);
	int now=0;
	for(int i=0;i<=qsum;++i)
	{
		while(now<q[i].r) modify_edge(1,++now,1);
		q[i].ans=query_edge(1,q[i].z);
	}
	sort(q,q+qsum+1,cmp);
	for(int i=1;i<=qsum;i+=2) printf("%lld
",((q[i].ans-q[i-1].ans)%mod+mod)%mod);
	return 0;
}

变式:([GXOI/GZOI2019]旧词)

求$sum _{ileq r} dep[LCA(i,z)]^k $,同一个数据点的k相同

由于没有 (l) 限制,所以可以不用把一个询问分成两个

还要求k次幂,之前给每个点加一的方法似乎不可行了,但是我们又不想放弃这种方法,所以考虑一种方法使得链修改可以忽略掉这个k次幂。

仔细思考后不难想到,对于一个点i,它的dep固定,那么(dep^k)也就是固定的,我们显然可以预处理出这个(dep^k),然后将它赋给,于是修改或者查询的时候都需要用覆盖次数乘上覆盖的这条链权值。

假设有一条链1->2->3,k=2,且LCA=3,如果分别赋值为1,4,9,那么这条链的权值就变成了14,然而我们需要的仅仅是9(因为只要求(dep[LCA]^k)),为了避免这样的重复计算,我们可以使用差分,那么上述三个点权值为1,3,5,这时就可以使用链查询来查询了,即
val[i]=$dep[i]^k $ - $ dep [fa[i]]^k$

总之这道题在上面那道题的基础上给每个点都赋了权值,并且在覆盖时还要乘上对应链的权值

Code:(与上面不同的部分)


//增加或修改函数

void build(int rt,int l,int r)
{
	if(l==r) {sum[rt]=0;sumval[rt]=val[rev[l]];return;}
	int mid=(l+r)>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
	sumval[rt]=(sumval[rt<<1]+sumval[rt<<1|1])%mod;
}

void add_tag(int rt,ll val)
{
	tag[rt]=(tag[rt]+val)%mod;
	sum[rt]=(sum[rt]+sumval[rt]*val%mod)%mod;
}

//主函数部分增加

for(int i=1;i<=n;++i) val[i]=(quickpow((ll)dep[i],k)-quickpow((ll)(dep[i]-1),k))%mod;
build(1,1,hfu);
int now=0;
for(int i=1;i<=m;++i)
{
	while(now<q[i].r) modify_edge(1,++now,1);
	q[i].ans=query_edge(1,q[i].z);
}
sort(q+1,q+m+1,cmp);
for(int i=1;i<=m;++i) printf("%lld
",(q[i].ans%mod+mod)%mod);
    
    
原文地址:https://www.cnblogs.com/Chtholly/p/11240499.html