【3】做题心得 - 2025 NOIP #68 - T2【链表】【神人】

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
struct cast{ int ax,ay,bx,by; }a[N];
int n,lasted,deleted,si[N];
bool cmpAX(int x,int y){ return a[x].ax<a[y].ax; }
bool cmpBX(int x,int y){ return a[x].bx>a[y].bx; }
bool cmpAY(int x,int y){ return a[x].ay<a[y].ay; }
bool cmpBY(int x,int y){ return a[x].by>a[y].by; }
struct mlist{ int nxt[N],prv[N],hd; }axl,ayl,bxl,byl;
void Push(mlist &x,int val){
	x.prv[val]=0;
	x.nxt[val]=x.hd;
	x.prv[x.hd]=val;
	x.hd=val;
}
void Pop(mlist &x,int val){
	x.prv[x.nxt[val]]=x.prv[val];
	x.nxt[x.prv[val]]=x.nxt[val];
	if(x.hd==val) x.hd=x.nxt[val]; 	
}
bool cutter(){
	if(lasted==1) return 1;
	int updated=0;
	int ax=axl.hd,ay=ayl.hd,bx=bxl.hd,by=byl.hd;
	int rx=0     ,ry=0     ,lx=1e9   ,ly=1e9   ;
	for(int i=1;i<=lasted/2;i++){
		rx=max(rx,a[ax].bx); ax=axl.nxt[ax]; if(rx<=a[ax].ax){ updated=1, deleted=i; for(int j=1,p=axl.hd;j<=i;j++,p=axl.nxt[p])si[j]=p; break; }
		ry=max(ry,a[ay].by); ay=ayl.nxt[ay]; if(ry<=a[ay].ay){ updated=1, deleted=i; for(int j=1,p=ayl.hd;j<=i;j++,p=ayl.nxt[p])si[j]=p; break; }
		lx=min(lx,a[bx].ax); bx=bxl.nxt[bx]; if(lx>=a[bx].bx){ updated=1, deleted=i; for(int j=1,p=bxl.hd;j<=i;j++,p=bxl.nxt[p])si[j]=p; break; }
		ly=min(ly,a[by].ay); by=byl.nxt[by]; if(ly>=a[by].by){ updated=1, deleted=i; for(int j=1,p=byl.hd;j<=i;j++,p=byl.nxt[p])si[j]=p; break; }
	}
	if(!updated) return 0;
	lasted-=deleted;
	for(int i=1;i<=deleted;i++)
		Pop(axl,si[i]),
		Pop(bxl,si[i]),
		Pop(ayl,si[i]),
		Pop(byl,si[i]);
	if(!cutter()) return 0;
	axl.hd=0; sort(si+1,si+deleted+1,cmpAX); for(int i=deleted;i>=1;i--) Push(axl,si[i]);
	ayl.hd=0; sort(si+1,si+deleted+1,cmpAY); for(int i=deleted;i>=1;i--) Push(ayl,si[i]);
	bxl.hd=0; sort(si+1,si+deleted+1,cmpBX); for(int i=deleted;i>=1;i--) Push(bxl,si[i]);
	byl.hd=0; sort(si+1,si+deleted+1,cmpBY); for(int i=deleted;i>=1;i--) Push(byl,si[i]);
	lasted=deleted;
	return cutter();
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i].ax>>a[i].ay>>a[i].bx>>a[i].by, si[i]=i;
	axl.hd=0; sort(si+1,si+n+1,cmpAX); for(int i=n;i>=1;i--) Push(axl,si[i]);
	ayl.hd=0; sort(si+1,si+n+1,cmpAY); for(int i=n;i>=1;i--) Push(ayl,si[i]);
	bxl.hd=0; sort(si+1,si+n+1,cmpBX); for(int i=n;i>=1;i--) Push(bxl,si[i]);
	byl.hd=0; sort(si+1,si+n+1,cmpBY); for(int i=n;i>=1;i--) Push(byl,si[i]);
	lasted=n;
	cout<<(cutter()?"YES\n":"NO\n");
	return;
}
int main(){
	freopen("kingdom.in","r",stdin);
	freopen("kingdom.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin>>T;
	while(T--) solve();	
	return 0;
}