洛谷P4216

算法:树状数组+离线思想+倍增LCA

时间复杂度:\(O(nlogn)\)(假设点数,边数与询问数相同)

第一问显然,为两者距离加\(1\),可以用LCA算出。(加\(1\)是因为算的是点的个数,而两者距离则是边的个数)

第二问,设当前有一个询问\((x,y,c)\),当前时间为\(now\),考虑什么点才会对这个询问产生贡献。

不难得出,这个点需要满足两个条件

\(1\).这个点在\(x\)到\(y\)的路径上

\(2\).这个点有一个时间戳(即这个点最开始被派任务的时间)设为\(t\),且\(now-t>c\)(即算出这个点的现在的危险值与\(c\)比较)。

对第二个条件进行转化,变为\(now-c>t\),将不同属性(即\(now\)和\(c\)是现在的属性,\(t\)是过去的属性)的变量分开。

结合第一个条件,不难得出询问的本质:问\(x\)到\(y\)的路径上有多少个点的时间戳小于\(now-c\),而且带修改。

先将问题简化,考虑不带修(即最开始每个点都有一个时间戳)。

转化问题,设\(sum[x]\)表示从\(x\)到根这一条路径上小于当前询问\(now-c\)的点的个数,那么对于当前询问答案就是\(sum[x]+sum[y]-sum[LCA(x,y)]-sum[father[LCA(x,y)]]\)

考虑离线转化,将询问记录在每个点上,然后使用dfs遍历,遍历到一个点的时候同时处理询问即可。

具体来说,用一个数组\(a\)记录所有时间戳的个数,\(a[i]\)表示时间戳为\(i\)的点有多少个。

在dfs的时候,遍历到当前点\(i\),就让\(a[dfn[i]]++\),处理与\(i\)有关的询问,然后继续遍历,在从\(i\)回溯之前,就让\(a[dfn[i]]--\)。每次处理询问查询的都是一个区间和,用树状数组维护即可。每次刚开始对一个点处理询问时,树状数组记录的都是从\(i\)到根这一条路径上所有点的不同的时间戳个数。不难得出,这种方法是正确的。

事实上,这种树上离线的思想非常重要,各位可以记下来。另有一道题:NOIP天天爱跑步,用了类似的思想,感兴趣的可以去挑战一下

回到本题,带修怎么办?

观察\(now-c\),发现\(c\)为非负整数,所以在一个询问后面的修改的点的时间戳,并不能影响当前这个询问。所以我们可以一次性读入所有的时间戳,转化为上面的问题进行处理即可。

那如果\(c\)可以为负数怎么办?

不用想的太复杂,此时的答案显然就跟第一问的答案相同。

code

#define ll long long
#define ull unsigned long long
using namespace std;
const int N=2e5+10;
int n,m,q;
int dep[N],f[N][25],dis[N],ans[N],col[N],fa[N];
int End[N<<1],Last[N],Next[N<<1];
int c[N];
struct Node
{
	int dif,id,mark;
}temp;
vector<Node> query[N];
int read() 
{
    int x=0,f=1;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-f;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-48;s=getchar();}
    return x*f;
}
int tot;
void add(int x,int y)
{
	End[++tot]=y,Next[tot]=Last[x],Last[x]=tot;
}
void deal_first(int x,int fa)
{
	dep[x]=dep[fa]+1;
	for(int i=1;i<=20;i++)
	f[x][i]=f[f[x][i-1]][i-1];
	for(int i=Last[x];i;i=Next[i])
	{
		int u=End[i];
		if(u==fa) continue;
		f[u][0]=x;
		deal_first(u,x);
	}
}
int LCA(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=20;i>=0;i--)
	{
		if(dep[f[x][i]]>=dep[y])
		x=f[x][i];
		if(x==y) return x;
		if(dep[x]==dep[y]) break;
	}
	for(int i=20;i>=0;i--)
	if(f[x][i]!=f[y][i])
	{
		x=f[x][i];
		y=f[y][i];
	}
	return f[x][0];
}
void modify(int x,int d)
{
	for(;x<=q;x+=x&-x)
	c[x]+=d;
 } 
int ask(int x)
{
	int res=0;
	for(;x>=1;x-=x&-x)
	res+=c[x];
	return res;
}
void dfs(int x,int fa)
{
	if(col[x])
	modify(col[x],1);
	for(int i=0;i<query[x].size();i++)
	ans[query[x][i].id]+=ask(query[x][i].dif-1)*query[x][i].mark;
	for(int i=Last[x];i;i=Next[i])
	{
		int u=End[i];
		if(u==fa) continue;
		dfs(u,x);
	}
	if(col[x])
	modify(col[x],-1);
}
int main() 
{
	int cnt=0,Root;
	n=read();
	for(int i=1,u;i<=n;i++)
	{
		u=read();
		fa[i]=u;
		if(!u)
		{
			Root=i;
			continue;
		}
		add(u,i);
		add(i,u);
	} 
	deal_first(Root,0);
	q=read();
	int x,y,c;
	for(int i=1;i<=q;i++)
	{
		int op=read();
		if(op==1)
		{
			cnt++;
			x=read(),y=read();
			c=read();
			temp.id=cnt;
			temp.dif=i-c;
			temp.mark=1;
			query[x].push_back(temp);
			query[y].push_back(temp);
			temp.mark=-1;
			int lca=LCA(x,y);
			query[lca].push_back(temp);
			query[fa[lca]].push_back(temp);
			dis[cnt]=dep[x]+dep[y]-(dep[lca]<<1);
		}
		else col[read()]=i;
	} 
	dfs(Root,0);
	for(int i=1;i<=cnt;i++)
	printf("%d %d\n",dis[i]+1,ans[i]);
    return 0;
}
上一篇:恩欧挨批模拟式题-50


下一篇:观察