动态开店线段树全RE求调
查看原帖
动态开店线段树全RE求调
786605
xgw120121楼主2025/8/30 14:54

RT

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int cnt,n,m,rt;
long long ans;
struct node{
	int x,l,r,bo;
}a[N<<1];
int lzy[N<<8];
struct tree{
    int sum,ls,rs;	
}t[N<<8];
int cmp(node a,node b)
{
	return a.x<b.x;
}
void pushdown(int p,int l,int r)
{
	if(lzy[p]==0) return;
	if(!t[p].ls) t[p].ls=++cnt;
	if(!t[p].rs) t[p].rs=++cnt;
	int k=lzy[p];lzy[p]=0;
	lzy[t[p].ls]+=k;lzy[t[p].rs]+=k;
	int mid=l+r>>1;
	t[t[p].ls].sum+=k*(mid-l+1);
	t[t[p].rs].sum+=k*(r-mid);
}
void pushup(int p)
{
	t[p].sum=t[t[p].ls].sum+t[t[p].rs].sum;
}
void update(int &p,int l,int r,int x,int y,int k)
{
	if(!p) p=++cnt;
//	cout<<p<<'\n';_sleep(500);
	if(x<=l&&r<=y) 
	{
		lzy[p]+=k;
		t[p].sum+=(r-l+1)*k;
		return;
	}
	pushdown(p,l,r);
	int mid=l+r>>1;
	if(x<=mid) update(t[p].ls,l,mid,x,y,k);
	if(mid+1<=y) update(t[p].rs,mid+1,r,x,y,k);
	pushup(p);
}
int query(int p,int l,int r)
{
	if(t[p].sum==0) return r-l+1;
	if(l==r) return 0;
	pushdown(p,l,r);
	int mid=l+r>>1;
	return query(t[p].ls,l,mid)+query(t[p].rs,mid+1,r);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int x,y,xx,yy;
		cin>>x>>y>>xx>>yy;
		a[++m].x=x;a[m].l=y;a[m].r=yy;a[m].bo=1;
		a[++m].x=xx;a[m].l=y;a[m].r=yy;a[m].bo=-1;
	}
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=m;i++)
	{
//		cout<<1e9-query(rt,1,1e9)-1<<'\n';
		ans+=1ll*(a[i].x-a[i-1].x)*max(0,int(1e9-query(rt,1,1e9)-1));
		update(rt,1,1e9,a[i].l,a[i].r,a[i].bo);
	}
	cout<<ans;
	return 0;
}
/*
2
100 100 200 200
150 150 250 255
*/
2025/8/30 14:54
加载中...