蒟蒻代码求助
查看原帖
蒟蒻代码求助
1065071
Atserckcn楼主2024/5/26 20:15

代码:

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll MAXN=1e5+5;
ll n,tl,tr,mid;
ll x1,x2,y1,y2;
ll s[MAXN],ans;
struct TREE{
	ll l,r,sum,lz;
}tree[MAXN<<4];
struct XY{
	ll x,y1,y2;
	ll flag;
}xy[MAXN<<3];
inline void read(ll &number)
{
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') number=-number;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		number=(number<<1)+(number<<3)+(ch-'0');
		ch=getchar();
	}
	return;
}
void pushup(ll p)
{
	if(!tree[p].lz)
		tree[p].sum=tree[p<<1].sum+tree[(p<<1)|1].sum;
	else tree[p].sum=tree[p].r-tree[p].l;
	return;
}
void build(ll l,ll r,ll p)
{
	tree[p].l=s[l];
	tree[p].r=s[r];
	if(l-r<=1) return;
	mid=(l+r)>>1;
	build(l,mid,p<<1);
	build(mid+1,r,(p<<1)|1);
	return;
}
bool cmp(XY a,XY b)
{
	return a.x<b.x;
}
void upd(ll y1,ll y2,ll p,ll flag)
{
	if(tree[p].l>=y1&&tree[p].r<=y2)
	{
		tree[p].lz+=flag;
		pushup(p);
		return;
	}
	if(tree[p<<1].r>y1)
		upd(y1,min(tree[p<<1].r,y2),p<<1,flag);
	if(tree[p<<1|1].l<y2)
		upd(max(tree[p<<1|1].l,y1),y2,(p<<1)|1,flag);
	pushup(p);
	return;
}
signed main(){
	read(n);
	for(ll i=1;i<=n;i++)
	{
		read(x1),read(y1),read(x2),read(y2);
		xy[i].x=x1;
		xy[i].y1=y1;
		xy[i].y2=y2;
		xy[i].flag=1;
		xy[i+n].x=x2;
		xy[i+n].y1=y1;
		xy[i+n].y2=y2;
		xy[i+n].flag=-1;
		s[i+1]=y1;
		s[i+1+n]=y2;
	}
	sort(s+1,s+2*n+1);
	sort(xy+1,xy+2*n+1,cmp);
	build(1,1,(n<<1)|1);
	upd(y1,y2,1,1);
	for(ll i=1;i<(n<<1);i++)
	{
		ans+=(xy[i].x-xy[i-1].x)*tree[i].sum;
		upd(xy[i].y1,xy[i].y2,1,xy[i].flag);
	}
	printf("%lld\n",ans);
	return 0;
}

结果:死循环

2024/5/26 20:15
加载中...