题目描述

在 COWVID-19 爆发期间 Farmer John 的奶牛们为了安全进行了隔离，

她们想到了一种全新的方式缓解无聊：研究高等物理！

事实上，她们甚至成功发现了一种新的亚原子粒子，她们将其命名为“哞粒子”。

奶牛们正在进行一项有关 N 个哞粒子的实验。

粒子 i 的“自旋”可以用范围在 $−10^9…10^9$ 之间的两个整数 xi 和 yi 来描述。

有时两个哞粒子会发生相互作用。

自旋为 (xi,yi) 和 (xj,yj) 的两个粒子之间仅当 xi≤xj 并且 yi≤yj 时会发生相互作用。

在这些条件下，有可能这两个粒子中的一个会消失（另一个粒子不会发生任何变化）。

在任意给定的时刻，至多只有一次相互作用会发生。

奶牛们想要知道在经过一些任意的相互作用之后剩余的哞粒子的最小数量。

样例

输入
$4$
$1 0$
$0 1$
$-1 0$
$0 -1$
输出
$1$

心路历程解题思路

今天上午模拟赛做了这道题。一开始把每个粒子看成一条线段，以为是要贪心或者DP，后来听老师讲解才猛然想到可以看成平面上的点。这样暴力算法就很明显了，先把所有点按横坐标排序，对于平面上的某个点，所有在它左下方的点都可以合并到它身上，因此并查集可以做到$O(n^2)$。进一步优化，我们发现当枚举到某个点时，若其左边的所有点（包括它自己）的纵坐标的最小值都大于右边所有点的最大值，（这意味着右边所有点在左边任意一个点的右下方），此时一定无法再合并，答案+1.

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_mair
#define pb push_back
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define rep(i,a,b) for(register int i=(a);i<=(b);++i)
#define per(i,a,b) for(register int i=(a);i>=(b);--i)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
template<class T> inline void read(T &x){
    x=0;char c=getchar();int f=1;
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();} x*=f;
}
const int N=100010;

int n;
Pii p[N];
int fre[N],back[N];

int main(){
    read(n);
    rep(i,1,n) read(p[i].fi),read(p[i].se);
    sort(p+1,p+1+n);

    fre[0]=1e9;back[n+1]=-1e9;
    rep(i,1,n) fre[i]=min(fre[i-1],p[i].se);
    per(i,n,1) back[i]=max(back[i+1],p[i].se);

    int res=0;
    rep(i,1,n) 
        if(fre[i]>back[i+1]) res++;
    cout<<res<<endl;

    return 0; 
}