【Codeforces 475F】—Meta-universe（Set）

传送门

考虑从$x,y$一起从外向内扫
找到第一个可以分开的地方就分开
复杂度是$O(nlog^2n)$的

开始手写了个结构体莫名一直$RE$
换成$pair$重写了一次就过了

#include<bits/stdc++.h>
using namespace std;
const int RLEN=1<<20|1;
inline char gc(){
    static char ibuf[RLEN],*ib,*ob;
    (ob==ib)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
    return (ob==ib)?EOF:*ib++;
}
#define gc getchar
inline int read(){
    char ch=gc();
    int res=0,f=1;
    while(!isdigit(ch))f^=ch=='-',ch=gc();
    while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
    return f?res:-res;
}
#define ll long long
#define re register
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define cs const
#define bg begin
#define rbg rbegin
cs int N=100005;
pii p[N];
inline pii swp(cs pii &fi){
	return pii(fi.se,fi.fi);
}
#define IT set<pii>::iterator
#define rIT set<pii>::reverse_iterator
inline int solve(set<pii> &st1,set<pii> &st2){
	if(st1.size()==1)return 1;
	IT lx=st1.bg();rIT rx=st1.rbg();
	IT ly=st2.bg();rIT ry=st2.rbg();
	IT End=st1.end();End--;
	while(lx!=End){
		int pre=(*lx).fi,now;
		lx++,now=(*lx).fi;
		if(now-pre>1){
			set<pii> st3,st4;
			while((*st1.bg()).fi<=pre){
				pii xx=*st1.bg();
				st3.insert(xx),st4.insert(swp(xx));
				st1.erase(xx),st2.erase(swp(xx));
			}
			return solve(st3,st4)+solve(st1,st2);
		}
		pre=(*rx).fi;
		rx++,now=(*rx).fi;
		if(pre-now>1){
			set<pii> st3,st4;
			while((*st1.rbg()).fi>=pre){
				pii xx=*st1.rbg();
				st3.insert(xx),st4.insert(swp(xx));
				st1.erase(xx),st2.erase(swp(xx));
			}
			return solve(st3,st4)+solve(st1,st2);
		}
		pre=(*ly).fi;
		ly++,now=(*ly).fi;
		if(now-pre>1){
			set<pii> st3,st4;
			while((*st2.bg()).fi<=pre){
				pii xx=*st2.bg();
				st3.insert(swp(xx)),st4.insert(xx);
				st1.erase(swp(xx)),st2.erase(xx);
			}
			return solve(st3,st4)+solve(st1,st2);
		}
		pre=(*ry).fi;
		ry++,now=(*ry).fi;
		if(pre-now>1){
			set<pii> st3,st4;
			while((*st2.rbg()).fi>=pre){
				pii xx=(*st2.rbg());
				st3.insert(swp(xx)),st4.insert(xx);
				st1.erase(swp(xx)),st2.erase(xx);
			}
			return solve(st3,st4)+solve(st1,st2);
		}
	};
	return 1;
}
set<pii> st1;
set<pii> st2;
int n;
int main(){
	n=read();
	for(int i=1;i<=n;i++){
		p[i].fi=read(),p[i].se=read();
		st1.insert(p[i]);
		st2.insert(swp(p[i]));
	}
	cout<<solve(st1,st2)<<'
';
}