【悬1关】扫描线板子求调
查看原帖
【悬1关】扫描线板子求调
659165
mysterys楼主2024/8/13 16:52
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl '\n'
const int N=1e5 + 5;
struct node{
	int val,l,r,opt;
}a[N<<1];
int b[N<<1];
int m,cnt,n,ans;
namespace T{
	struct node{
		int l,r,minn,num,len,lzy;
	}t[N<<3];
	inline void up(int u){
		t[u].minn=min(t[u<<1].minn,t[u<<1|1].minn);
		t[u].num=0;
		if(t[u].minn==t[u<<1].minn) t[u].num+=t[u<<1].num;
		if(t[u].minn==t[u<<1|1].minn) t[u].num+=t[u<<1|1].num;
	}
	inline void down(int u){
		if(!t[u].lzy) return ;
		t[u<<1].lzy+=t[u].lzy;t[u<<1|1].lzy+=t[u].lzy;
		t[u<<1].minn+=t[u<<1].lzy;t[u<<1|1].minn+=t[u<<1|1].lzy;
		t[u].lzy=0;
	}
	inline void build(int u,int l,int r){
		t[u].l=l;t[u].r=r;
		t[u].len=b[r+1]-b[l];
		if(l==r){
			t[u].num=t[u].len;
			return ;
		}
		int m= (l+r)>>1;
		build(u<<1,l,m);
		build(u<<1|1,m+1,r);
		up(u);
	}
	inline void upd(int u,int l,int r,int v){
		if(t[u].l>=l&&t[u].r<=r){
			t[u].minn+=v;
			t[u].lzy+=v;
			return;
		}
		down(u);
		int m= (t[u].l+t[u].r) >>1;
		if(l<=m) upd(u<<1,l,r,v);
		if(r>m) upd(u<<1|1,l,r,v);
		up(u);
	}
	inline int ask(int u,int l,int r){
		if(t[u].l>=l&&t[u].r<=r) {
			if(t[u].minn>0) return t[u].num;
			else return t[u].len-t[u].num;
		} 
		int m=(t[u].l+t[u].r)>>1;
		int res=0;
		if(l<=m) res=ask(u<<1,l,r);
		if(r>m) res+=ask(u<<1|1,l,r);
		up(u);
		return res;
	}
}
signed main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	cout.tie(nullptr);
	cin>>n;
	for(int i=1;i<=n;i++){
		int X1,X2,Y1,Y2;
		cin>>X1>>Y1>>X2>>Y2;
		a[++m]=(node){X1,Y1,Y2,1};
		a[++m]=(node){X2,Y1,Y2,-1};
		b[++cnt]=Y1;
		b[++cnt]=Y2;
	}
	stable_sort(b+1,b+cnt+1);
	cnt=unique(b+1,b+cnt+1)-b-1;
	T::build(1,1,cnt-1);
	for(int i=1;i<=m;i++){
		a[i].l=lower_bound(b+1,b+cnt+1,a[i].l)-b;
		a[i].r=lower_bound(b+1,b+cnt+1,a[i].r)-b;
	}
	stable_sort(a+1,a+m+1,[&](node p1,node p2){
		return p1.val<p2.val;
	});
	for(int i=1;i<m;i++){
		if(a[i].l<a[i].r){
			T::upd(1,a[i].l,a[i].r-1,a[i].opt);
		}
		ans+=T::ask(1,1,cnt-1)*(a[i+1].val-a[i].val);
	}
	cout<<ans;
	return 0;
}

样例输出:15500

有事踹我,蟹蟹。

2024/8/13 16:52
加载中...