听灌佬多(悬关)
  • 板块灌水区
  • 楼主_zhaopeizhe2026_
  • 当前回复6
  • 已保存回复6
  • 发布时间2024/12/21 11:12
  • 上次更新2024/12/21 14:48:43
查看原帖
听灌佬多(悬关)
1063310
_zhaopeizhe2026_楼主2024/12/21 11:12
#include<bits/stdc++.h>
using namespace std;
struct node{
	int x,y,q;
	bool p;
}h[2][100005];
bool cmp(node a,node b){
	return a.q==b.q?a.p>b.p:a.q<b.q;
}
const int maxn=8e6;
int n,l[maxn],ls[maxn],rs[maxn],c[maxn],mxr=10000,mxl=-10000,tot;
void f(int w){
	if(!ls[w])ls[w]=++tot;
	if(!rs[w])rs[w]=++tot;
	int v=l[w];
	c[ls[w]]+=v;
	l[ls[w]]+=v;
	c[rs[w]]+=v;
	l[rs[w]]+=v;
	l[w]=0;
}
void find(int w,int lc,int rc,int x,int y,int v){
	if(x<=lc&&y>=rc){
		c[w]+=v;
		l[w]+=v;
		return;
	}
	if(l[w]!=0)f(w);
	int mid=(lc+rc)>>1;
	if(x<mid){
		if(!ls[w])ls[w]=++tot;
		find(ls[w],lc,mid,x,y,v);
	}
	if(y>mid){
		if(!rs[w])rs[w]=++tot;
		find(rs[w],mid,rc,x,y,v);
	}
}
int gs(int w,int lc,int rc){
	if(rc-lc!=1||((!ls[w])&&(!rs[w])))return (c[w]>0)*(rc-lc);
	if(l[w]!=0)f(w);
	int mid=(lc+rc)/2,tmp;
	if(ls[w])tmp+=gs(ls[w],lc,mid);
	if(rs[w])tmp+=gs(rs[w],mid,rc);
	return tmp;
}
int main(){
	int ans=0,a,b,c,d,lt,o;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a>>b>>c>>d;
		h[0][2*i-1].p=h[1][2*i-1].p=false;
		h[0][2*i].p=h[1][2*i].p=true;
		h[0][2*i-1].x=h[0][2*i].x=a;
		h[0][2*i-1].y=h[0][2*i].y=c;
		h[0][2*i].q=b;
		h[0][2*i-1].q=d;
		h[1][2*i-1].x=h[1][2*i].x=b;
		h[1][2*i-1].y=h[1][2*i].y=d;
		h[1][2*i].q=a;
		h[1][2*i-1].q=c;
	}
	n*=2;
	sort(h[0]+1,h[0]+n+1,cmp);
	sort(h[1]+1,h[1]+n+1,cmp);
	for(int i=0;i<2;i++){
		memset(ls,0,sizeof(ls));
		memset(rs,0,sizeof(rs));
		memset(c,0,sizeof(c));
		memset(l,0,sizeof(l));
		tot=1;
		lt=0;
		for(int j=1;j<=n;j++){
			if(h[i][j].p)find(1,mxl,mxr,h[i][j].x,h[i][j].y,1);
			else find(1,mxl,mxr,h[i][j].x,h[i][j].y,-1);
			o=gs(1,mxl,mxr);
			ans+=abs(o-lt);
			lt=o;
		}
	}
	return 0;
}
2024/12/21 11:12
加载中...