题目

题目大意

给你一颗带点权的树，后面有许多个询问\((u,v)\)，问：

\[\sum_{i=0}^{k-1}dist(u,d_i) \ or \ a_{d_i}
\]

\(d\)为\(u\)到\(v\)路径上的点。

思考历程&正解

其实我只会我的方法……题解说得太简略了，集训队大佬Infleaking的方法完全听不懂……

首先看到这道题，就立马觉得是神仙题。

但是想到既然是树题，那应该不会太难。

于是我开始试着\(LCT\)建立联系……但是发现这个操作真是太骚了，用\(splay\)真的不好维护。

再想想线段树，但显然线段树还是不行。

到了后来，我突然想到了一个特别傻逼的做法：\(ST\)表！

这道题维护的东西和\(2\)的次幂息息相关，所以再维护的时候，左右区间必须是\(2\)的次幂。

然后想一想怎么做。

首先答案加上\(\frac{k(k+1)}{2}\)，也就是\(dist\)的贡献。接着考虑加没有加上的贡献加上去。

我们可以找到满足\(2^i\leq k\)的最大\(i\)，然后将区间变成两段。

我们维护左边第\(i\)位为\(1\)的个数，记作\(suml\)。

那么答案就是\(suml*2^{i}+左边的答案+右边的答案\)。

由于左边的区间是整的，所以比较好预处理。

首先对于每一位，预处理出一个前缀和，记作\(sum_{i,j}\)。

设\(f_{i,j}\)表示\(i\)到\(2^j-1\)个祖先的答案。转移是显然的，就是将其分成两个长度相等的子区间，左右区间的答案之和，加上左区间的\(i-1\)位为\(1\)的个数乘上\(2^{i-1}\)。

同样地，也求\(g_{i,j}\)，定义和\(f_{i,j}\)相反。

如果路径是一条从后代到祖先的链，可以\(i\)从高到低枚举，如果\(2^i>k\)就加上区间内\(i\)位为\(1\)的个数乘上\(2^i\)；否则就分成两个区间，将左区间的贡献加上之后，后面的答案就跟左区间没有关系了，那么就可以把左区间裁掉，转化成只有右区间的子问题。

现在最重要的问题是如何绕过它们的\(LCA\)。

首先从\(u\)开始跳，如果要往右边跳\(2^i\)步，判断一下是否绕过\(LCA\)。如果没有绕过，就跳过去，跳到不能跳为止。

对于后面的，可以将这样做下去的所有区间的左端点给处理出来。我们考虑倒过来求，也就是从\(v\)开始，向上跳\(lowbit(k)\)位，不要越过\(LCA\)，跳到不能跳为止。用个栈将这些经过的点存起来。

于是就可以很容易地算出后面的这些区间的答案。然后我们就把后面的区间给裁掉了。

于是只剩下了那个长度为\(2\)的次幂的，跨过\(LCA\)的区间。

考虑暴力求。每次分成两段，求出两段的答案之后用和\(f\)一样的方法合并。接着我们就发现，这两段中至少有一段是被处理过的，只需要处理那段没有被处理的就行了。于是递归的过程只有\(\lg\)层。

然后就没有然后了。时间复杂度是优秀的\(O(n\lg n)\)，实际上常数巨大无比……

而且代码实现不容易。

代码

using namespace std;

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cassert>

#define N 300010

inline int input(){

	char ch=getchar();

	while (ch<'0' || '9'<ch)

		ch=getchar();

	int x=0;

	do{

		x=x*10+ch-'0';

		ch=getchar();

	}

	while ('0'<=ch && ch<='9');

	return x;

}

int n,a[N];

struct EDGE{

	int to;

	EDGE *las;

} e[N*2];

int ne;

EDGE *last[N];

int dep[N],fa[N][30];

long long sum[N][30],f[N][30],g[N][30];

inline void init(){

	static int q[N];

	int head=1,tail=1;

	q[1]=1;

	while (head<=tail){

		int x=q[head++];

		for (int i=0;i<29;++i)

			sum[x][i]=sum[fa[x][0]][i]+(a[x]>>i&1);

		dep[x]=dep[fa[x][0]]+1;

		f[x][0]=g[x][0]=0;

		for (int i=1;1<<i<=dep[x];++i){

			fa[x][i]=fa[fa[x][i-1]][i-1];

			f[x][i]=f[x][i-1]+f[fa[x][i-1]][i-1]+(sum[x][i-1]-sum[fa[x][i-1]][i-1]<<i-1);

			g[x][i]=g[x][i-1]+g[fa[x][i-1]][i-1]+(sum[fa[x][i-1]][i-1]-sum[fa[x][i]][i-1]<<i-1);

		}

		for (EDGE *ei=last[x];ei;ei=ei->las)

			if (ei->to!=fa[x][0]){

				fa[ei->to][0]=x;

				q[++tail]=ei->to;

			}

	}

}

inline int LCA(int u,int v){

	if (dep[u]<dep[v])

		swap(u,v);

	for (int k=dep[u]-dep[v],i=0;k;k>>=1,++i)

		if (k&1)

			u=fa[u][i];

	if (u==v)

		return u;

	for (int i=18;i>=0;--i)

		if (fa[u][i]!=fa[v][i])

			u=fa[u][i],v=fa[v][i];

	return fa[u][0];

}

long long getsum(int u,int v,int lca,int k){

	return sum[u][k]+sum[v][k]-sum[lca][k]-sum[fa[lca][0]][k];

}

long long dfs(int k,int u,int v,int lca){

	if (v==lca)

		return f[u][k];

	if (dep[u]-dep[lca]<1<<k-1)

		return dfs(k-1,u,fa[v][k-1],lca)+g[v][k-1]+(getsum(u,fa[v][k-1],lca,k-1)<<k-1);

	return f[u][k-1]+dfs(k-1,fa[u][k-1],v,lca)+(sum[u][k-1]-sum[fa[u][k-1]][k-1]<<k-1);

}

int w[30],top;

int main(){

	freopen("c.in","r",stdin);

	freopen("c.out","w",stdout);

	n=input();

	int Q=input();

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

		a[i]=input();

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

		int u=input(),v=input();

		e[ne]={v,last[u]};

		last[u]=e+ne++;

		e[ne]={u,last[v]};

		last[v]=e+ne++;

	}

	init();

	while (Q--){

		int u=input(),v=input(),lca=LCA(u,v),k=dep[u]+dep[v]-dep[lca]*2+1,i;

		long long ans=(long long)(k-1)*k>>1;

		for (i=29;i>=0 && k;--i)

			if (k>>i&1){

				if (1<<i<=dep[u] && dep[lca]-1<=dep[fa[u][i]]){

					ans+=f[u][i]+(sum[u][i]-sum[fa[u][i]][i]<<i);

					u=fa[u][i];

					k-=1<<i;

				}

				else

					break;

			}

			else

				ans+=getsum(u,v,lca,i)<<i;

		top=0;

		w[0]=v;

		if (u==fa[lca][0])

			i++;

		for (int j=0;j<i;++j)

			if (k>>j&1){

				++top;

				w[top]=fa[w[top-1]][j];

			}

		int x=w[top];

		for (int j=i-1;j>=0;--j)

			if (k>>j&1){

				--top;

				ans+=g[w[top]][j]+(sum[w[top]][j]-sum[fa[w[top]][j]][j]<<j);

			}

			else

				ans+=sum[v][j]-sum[w[top]][j]<<j;

		if (u!=fa[lca][0])

			ans+=dfs(i,u,x,lca)+(getsum(u,x,lca,i)<<i);

		printf("%lld\n",ans);

	}

	return 0;

}

总结

在遇到位运算和各种询问结合起来的问题时，要想到\(ST\)表……

巴特西

[JZOJ6341] 【NOIP2019模拟2019.9.4】C

题目

题目大意

思考历程&正解

代码

总结

最新文章

热门文章