题解：AT_joisc2013_spy スパイ (Spy)

这道题我一直在想怎么用扫描线来做，后面实在是没招了，然后再仔细一看数据范围，发现只要

O(n^2+m)

就可以过了。

进入正题，我们先转换一下题目。对于每个间谍计划输入的

x

，

y

，它们以及它们的所有下属都会进行工作，也就是说，在 JOI 社形成的树中，以 $x$ 为根节点的子树都会被覆盖到；在 IOI 社形成的树中，以 $y$ 为根节点的子树都会被覆盖到，而对于任意一个点

i

，完成任务的条件就是同时被两棵树覆盖到，也就是说这个点要在 $x$ 的子树里，也要在 $y$ 的子树里。

那么如何处理这个问题呢？我们可以使用 DFS 序来解决这个问题。

设在深搜时

u

的进栈时间为

dfn_u

，以

u

为根的子树大小为

siz_u

，对于

[dfn_u，dfn_u+siz_u]

，若存在节点

k

，使得

dfn_k

在这个区间范围之内，则

k

为

u

或

u

的子树中的节点。

设 JOI 社，IOI 社形成的树的 DFS 序分别为

dfn1

，

dfn2

，子树大小分别为

siz1

，

siz2

那么对于查询

i

完成了多少个任务，就变成了求在输入给出的

M

个二元组中，有多少个二元组

x

，

y

满足：

\begin{aligned}dfn1_x\le dfn1_i\le dfn1_x+siz1_x\end{aligned}

\begin{aligned}dfn2_y\le dfn2_i\le dfn2_y+siz2_y\end{aligned}

这个式子长得很像二维偏序，~~但是我不会打~~。所以我们重新看一下数据范围，发现

n

不超过

2000

，且

dfn+siz

的值不会超过

n

。

于是我们可以再转换一下来求上面那个式子。我们把

(dfn1_i,dfn2_i)

这个二元组视作二维平面上的一个点，那么

dfn1_i

为横坐标，

dfn2_i

为纵坐标，上面那个不等式在平面上就相当于一个矩形，这个矩形以 $(dfn1_x,dfn2_y)$ 为左下角，以 $(dfn1_x+siz1_x,dfn2_y+siz2_y)$ 为右上角。而我们的目标，也就是求有多少个这样的矩形包含了 $(dfn1_i,dfn2_i)$ 这个点。

那么，我们就可以运用二维差分的思想，每次读入一个二元组

x

和

y

就把上述矩形部分全部加

1

，查询的时候看有多少个矩形覆盖了

(dfn1_i,dfn2_i)

这个点即可求出

i

这个员工完成了多少个任务。

差分部分时间复杂度

O(n^2+m)

，每个查询

O(1)

，总复杂度

O(n^2+m)

可以通过本题。

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10,M=5e5+10;
int dfn1[N],dfn2[N],num=0,siz1[N],siz2[N];
vector<int> g[N],p[N];
inline void dfs(int u,int fa){
	dfn1[u]=++num;
	siz1[u]=1;
	for(int v:g[u]){
		if(v==fa)continue;
		dfs(v,u);
		siz1[u]+=siz1[v];
	}
	return;
}
inline void dfs2(int u,int fa){
	dfn2[u]=++num;
	siz2[u]=1;
	for(int v:p[u]){
		if(v==fa)continue;
		dfs2(v,u);
		siz2[u]+=siz2[v];
	}
	return;
}
int n,m,root1,root2,q;//第一棵树的根节点和第二棵树的根节点 
int s[N][N];
inline void update(int x,int y,int a,int b){//将以(x,y)为左下角,(a,b)为右上角的矩形全部加1 
	s[x][y]+=1;
	s[x][b+1]-=1;
	s[a+1][y]-=1;
	s[a+1][b+1]+=1; 
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1,x,y;i<=n;i++){
		cin>>x>>y;
		if(x!=0)g[x].push_back(i),g[i].push_back(x);
		else root1=i;
		if(y!=0)p[y].push_back(i),p[i].push_back(y);
		else root2=i;
	}
	dfs(root1,0);
	num=0;dfs2(root2,0);
	//for(int i=1;i<=n;i++)cout<<"dfn1["<<i<<"]="<<dfn1[i]<<" ";cout<<"\n"; for(int i=1;i<=n;i++)cout<<"dfn2["<<i<<"]="<<dfn2[i]<<" ";cout<<"\n";
	for(int i=1,x,y;i<=m;i++){
		cin>>x>>y;
		update(dfn1[x],dfn2[y],dfn1[x]+siz1[x]-1,dfn2[y]+siz2[y]-1);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
			//cout<<s[i][j]<<" ";
		}
		//cout<<"\n";
	}
	for(int i=1;i<=n;i++)cout<<s[dfn1[i]][dfn2[i]]<<"\n";	
	return 芙芙天下第一！;
}

题解：AT_joisc2013_spy スパイ (Spy)

文章操作

相关推荐

评论

题解：AT_joisc2013_spy スパイ (Spy)