点此看题面
对于当前右下角\((x,y)\),容易想到去找到满足\(a\le x,b\le y\)的所有尚未匹配的左上角\((a,b)\)中\(b\)最大的那个,让\((a,b)\)和\((x,y)\)匹配。
然后发现其实这是唯一构造方案,因为假设选择了另一个满足\(c\le x,d\le y\)的尚未匹配的左上角\((c,d)\),则\((a,b)\)要么被困在了矩形内(\(a\ge c\)),要么就因为这个矩形的阻隔再也不可能匹配了(\(a<c\))。
既然如此,只需判断这个方案是否合法即可。
先考虑按照横坐标顺序枚举,判断纵方向上是否存在相交区间。(之后还要把横纵坐标交换再检验一遍)
这里要先提一个细节,就是横坐标相同时同类型区间(类型指加入/删除)不能存在包含关系,要特殊判断。(当然更不能相交,但相交在之后会一起判掉)
而要判是否存在区间相交,考虑我们把记下所有端点,则当前区间\([l,r]\)中不能包含任何一个已有的端点。
只需找到大于等于\(l\)的第一个点判断是否在\([l,r]\)中即可,可以直接用一个\(set\)维护下所有端点。
#include<bits/stdc++.h> #define Tp template<typename Ty> #define Ts template<typename Ty,typename... Ar> #define Reg register #define RI Reg int #define Con const #define CI Con int& #define I inline #define W while #define N 100000 #define NA() (puts("syntax error"),exit(0))//无解 using namespace std; int n,ans[N+5]; struct P {int p,x,y;I bool operator < (Con P& o) Con {return x^o.x?x<o.x:y<o.y;}}p[2*N+5]; struct OP {int x,l,r,op;I bool operator < (Con OP& o) Con {return x^o.x?x<o.x:(op^o.op?op<o.op:l<o.l);}}w[2*N+5]; set<pair<int,int> > S;I void Get()//构造方案 { set<pair<int,int> >::iterator it;sort(p+1,p+2*n+1);for(RI i=1;i<=2*n;++i) { if(p[i].p<=n) {S.insert(make_pair(p[i].y,p[i].p));continue;}//左上角 ((it=S.lower_bound(make_pair(p[i].y+1,0)))==S.begin())&&(NA(),0),ans[(--it)->second]=p[i].p,S.erase(it);//右下角,找到纵坐标尽可能大的,找不到就无解 } } set<int> V;I void Check()//检验合法 { RI i;for(i=1;i<=n;++i) w[i]=(OP){p[i].x,p[i].y,p[ans[i]].y,1},w[i+n]=(OP){p[ans[i]].x+1,p[i].y,p[ans[i]].y,0}; RI o,lst[2]={0,0};for(sort(w+1,w+2*n+1),i=1;i<=2*n;++i)//特殊处理横坐标相同的区间 o=lst[w[i].op],lst[w[i].op]=i,w[o].x==w[i].x&&(w[o].l==w[i].l||w[o].r>=w[i].r)&&(NA(),0);//不能存在包含关系 set<int>::iterator it,jt;for(V.insert(0),V.insert(2e9),i=1;i<=2*n;++i)//扫描线 { if(!w[i].op) {it=V.find(w[i].l),w[i].l^w[i].r&&(V.erase(++(jt=it)),0),V.erase(it);continue;}//删除 *V.lower_bound(w[i].l)<=w[i].r&&(NA(),0),V.insert(w[i].l),V.insert(w[i].r);//加入,不能包含任何端点 } } I bool cmp(Con P& x,Con P& y) {return x.p<y.p;} int main() { RI i;for(scanf("%d",&n),i=1;i<=2*n;++i) scanf("%d%d",&p[i].x,&p[i].y),p[i].p=i; for(Get(),sort(p+1,p+2*n+1,cmp),Check(),i=1;i<=2*n;++i) swap(p[i].x,p[i].y);Check();//先构造方案,然后交换横纵坐标检验两次 for(i=1;i<=n;++i) printf("%d\n",ans[i]-n);return 0; }