自动搬运

查看原文

来自洛谷，原作者为

	xixiup Comrade Manvski

搬运于2025-08-24 22:19:18，当前版本为作者最后更新于2020-10-18 11:58:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

写在前面的话

苏格拉底曾指出，求得知识的最好办法是有系统的问与答，故本题解采用了该种方式。

思路分享

问：这道题你怎么看？

答：首先看到这道题时，我们可能会想到二位偏序，但是很遗憾地告诉大家，这道题用二位偏序并不能解决。

问：为什么不能解决呢？

答：考虑对于 $1$ 个点，若此时将这个点加入了树状数组中，那么如何计算它的贡献呢？我们并不能在给定的时间中将这个贡献计算出来。

问：那么我们该怎么做呢？

答：考虑转化为一道图论题，若粒子 $x$ 与粒子 $y$ 之间可以发生作用，就在粒子 $x$ 与粒子 $y$ 之间连一条无向边。

问：为什么要这么做呢？

答：因为我们可以发现，若一些粒子处于一个连通块中，那么这些粒子就可以经过一番相互作用之后变为 $1$ 个粒子，而若两个粒子不在一个连通块中，那么这两个连通块再怎么相互作用也只可能变成 $2$ 个粒子。

问：但是这样仍是 $\Theta(n^2)$ 的，怎么优化呢？

答：考虑使用二位偏序的思想，将这些点以 $y$ 为关键字排序，我们就可以仅考虑 $x$ 一维了。

问：那么如何计算答案呢？

答：考虑使用并查集的思想，若排序后，一个粒子可以与它前面的粒子相互作用，那么就将这两个点连接起来，否则就计算一次贡献。

问：乍一看感觉很对呢，这就是正解了吧？

答：先别着急，我们先来看看这个思路的代码实现。

#include<bits/stdc++.h>
using namespace std;
const int maxn=100100;
int n,Min;
struct node{
	int x,y;
	bool operator<(node u)const{
		return y==u.y?x>u.x:y<u.y;
	}//x坐标需要从大到小排序
	//因为如果两个粒子y坐标相同，那么x较大的更有可能与其他粒子互相作用，从而获得更小答案。
}moo[maxn];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%d%d",&moo[i].x,&moo[i].y);
	}
	stable_sort(moo+1,moo+1+n);
	Min=1000000001;
	moo[0].y=-1000000001;
	int ans=0;
	for(int i=1;i<=n;i++){
		if(moo[i].x<Min&&moo[i].y!=moo[i-1].y){
			ans++;//若与前面的粒子无法发生互相作用，那么将答案加1
		}
		Min=min(Min,moo[i].x);
	}
	printf("%d",ans);
	return 0;
}

答：看完之后，可以发现其实这个方法是错误的，只能通过前两个测试点（也就是两个样例）

问：为什么它是错的呢？乍一看感觉很对呢。

答：我们可以考虑如下图中的三个粒子。

答：按照这种方式排好序之后，我们就可以得到三个粒子 $1$、$2$、$3$。通过这份代码所计算出来的答案是 $2$ ，两次贡献分别在点 $1$ 与 $2$ 处产生，但是其实正确的答案为 $1$，即 $3$ 粒子与另外两个粒子互相作用并使这两个粒子消失。

问：那好吧。那么我们还可以怎样做呢？

答：我们不妨设 $l_i$ 为粒子 $1 \sim i$ 的 $x$ 坐标的最小值，$r_i$为粒子 $i \sim n$ 的 $x$ 坐标的最大值，那么我们可以发现，若对于某个粒子 $i$，若 $l_i > r_i+1$，即粒子 $i$ 前面的所有粒子的 $x$ 坐标最小值还要大于后面所有粒子的 $x$ 坐标最大值，那么又因为我们已经将所有粒子按照 $y$ 坐标从小到大排序了，那么对于所有 $i \in \left[ 1,i \right],j \in \left( i,n \right]$，都有 $x_i > x_j$ 且 $y_i \leqslant y_j$，即 $\left[ 1,i \right]$ 与 $\left( i,n \right]$ 不可能在一个连通块中，就可以将答案加 $1$。

问：那么这就是正解了吗？

答：是的。

正解代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=100100;
int n;
int l[maxn],r[maxn];
struct node{
	int x,y;
	bool operator<(node u)const{
		return y==u.y?x<u.x:y<u.y;
	}//与前面差不多的排序，但是y坐标相同时x坐标需改成从小到大
}moo[maxn];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%d%d",&moo[i].x,&moo[i].y);
	}
	stable_sort(moo+1,moo+1+n);
	l[1]=moo[1].x;
	for(int i=2;i<=n;i++){
		l[i]=min(l[i-1],moo[i].x);
	}//处理l
	r[n]=moo[n].x;
	for(int i=n-1;i>=1;i--){
		r[i]=max(r[i+1],moo[i].x);
	}//处理r
	int ans=1;//这里ans的初始值需要赋为1
	for(int i=1;i<n;i++){
		if(l[i]>r[i+1]){
			ans++;
		}
	}
	printf("%d",ans);
	return 0;
}