32分求助
查看原帖
32分求助
475419
AsoltA楼主2023/4/13 20:47
#include <bits/stdc++.h>
using namespace std;
int n,cnt,cnt2,mn=0,mx=20001,ans;
const int SZ=200005<<1;
struct st
{
	int x,y,p;
	bool cr;
} X[25005],Y[25005];
bool cmp(st s1,st s2)
{
	return s1.p<s2.p;
}
struct node
{
	int l,r,count,cover;
	int len(){return this->r-this->l+1;};
};
node tree[SZ];
void build(int p,int l,int r)
{
	tree[p].r=r,tree[p].l=l;
	if(l==r)
	{
		tree[p].count=1;
		tree[p].cover=0;
		return;
	}
	int mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	tree[p].count=tree[p<<1].count+tree[p<<1|1].count;
}
void upd(int p,int l,int r,int v)
{
	if(tree[p].l>r||tree[p].r<l) return;
	if(tree[p].l>=l&&tree[p].r<=r)
	{
		tree[p].cover+=v;
		return;
	}
	if(tree[p<<1].r>=l)
	{
		upd(p<<1,l,r,v);
	}
	if(tree[p<<1|1].l<=r)
	{
		upd(p<<1|1,l,r,v);
	}
	//printf("%d %d\n",tree[p].cover,tree[p].count);
}
int qry(int p,int l,int r)
{
	if(tree[p].l>r||tree[p].r<l) return 0;
	int sum=0;
	if(tree[p].l>=l&&tree[p].r<=r)
	{
		if(tree[p].cover)
		{
			return tree[p].count;
		}
		if(tree[p].l!=tree[p].r)
		{
			sum+=qry(p<<1,l,r);
			sum+=qry(p<<1|1,l,r);
			return sum;
		}
		return 0;
	}
	if(tree[p<<1].r>=l)
	{
		sum+=qry(p<<1,l,r);
	}
	if(tree[p<<1|1].l<=r)
	{
		sum+=qry(p<<1|1,l,r);
	}
	return sum;
}
int main()
{
	build(1,mn,mx); 
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
    	int aa,bb,cc,dd;
    	scanf("%d%d%d%d",&aa,&bb,&cc,&dd);
    	aa+=10000;
    	bb+=10000;
    	cc+=10000;
    	dd+=10000;
    	X[++cnt].cr=false;
    	X[cnt].x=aa;
    	X[cnt].y=cc;
    	X[cnt].p=bb; 
    	X[++cnt].cr=true;
    	X[cnt].x=aa;
    	X[cnt].y=cc;
    	X[cnt].p=dd;
    	Y[++cnt2].cr=false;
    	Y[cnt2].x=bb;
    	Y[cnt2].y=dd;
    	Y[cnt2].p=aa; 
    	Y[++cnt2].cr=true;
    	Y[cnt2].x=bb;
    	Y[cnt2].y=dd;
    	Y[cnt2].p=cc;
	}
	sort(X+1,X+cnt+1,cmp);
	sort(Y+1,Y+cnt2+1,cmp);
	for(int i=1;i<=cnt;i++)
	{
		int l1=qry(1,mn,mx);
		if(X[i].cr)
		{
			upd(1,X[i].x,X[i].y-1,-1);
		}
		else
		{
			upd(1,X[i].x,X[i].y-1,1);
		}
		int l2=qry(1,mn,mx);
		ans+=abs(l1-l2);
	}
	for(int i=1;i<=cnt2;i++)
	{
		int l1=qry(1,mn,mx);
		if(Y[i].cr)
		{
			upd(1,Y[i].x,Y[i].y-1,-1);
		}
		else
		{
			upd(1,Y[i].x,Y[i].y-1,1);
		}
		int l2=qry(1,mn,mx);
		ans+=abs(l1-l2);
	}
	printf("%d\n",ans);
	return 0;
}
2023/4/13 20:47
加载中...