【容斥+扫描线】2023CCPC河南省赛 I 数正方形

水深无声 2024-03-16 13:33 134阅读 0赞

**我不管，我要成为容斥高手！**

题意：

![b3f091ab046e449296e51bb9005a9f6d.png][]

思路：

官方题解：

![563bbe9d957a46e5b9ec6bac82221d8d.png][]

扫面线是单点修改和单点查询：

![cbd17e8a92f5451798c577446e65488f.jpeg][]

Code：

#include <bits/stdc++.h>
    
    #define y1 Y1
    #define int long long
    
    using namespace std;
    
    const int mxn=3e5+10;
    const int mxe=3e6+10;
    const int mxv=1e3+10;
    const int mod=1e9+7;
    
    struct Line{
    	int xa,xb,y,w;
    }a[mxn];
    
    struct ty{
    	int val;
    }tree[mxe<<2];
    
    int N;
    int x1,y1,x2,y2;
    
    bool cmp(Line x,Line y){
    	return x.y<y.y;
    }
    void pushup(int rt){
    	tree[rt].val=tree[rt<<1].val+tree[rt<<1|1].val;
    }
    void build(int rt,int l,int r){
    	if(l==r){
    		tree[rt].val=0;
    		return;
    	}
    	int mid=l+r>>1;
    	build(rt<<1,l,mid);
    	build(rt<<1|1,mid+1,r);
    	pushup(rt);
    }
    void change(int rt,int l,int r,int x,int k){
    	if(l==r){
    		tree[rt].val+=k;
    		return;
    	}
    	int mid=l+r>>1;
    	if(x<=mid) change(rt<<1,l,mid,x,k);
    	else change(rt<<1|1,mid+1,r,x,k);
    	pushup(rt);
    }
    int query(int rt,int l,int r,int x,int y){
    	if(x<=l&&r<=y){
    		return tree[rt].val;
    	}
    	int mid=l+r>>1;
    	int res=0;
    	if(x<=mid) res+=query(rt<<1,l,mid,x,y);
    	if(y>mid) res+=query(rt<<1|1,mid+1,r,x,y);
    	return res;
    }
    void solve(){
    	cin>>N;
    	int idx=0,ans=4*N*N;
    	for(int i=1;i<=N;i++){
    		cin>>x1>>y1>>x2>>y2;
    		a[++idx]={x1,x2,y1,1};
    		a[++idx]={x1,x2,y2,-1};
    		ans-=2*(x2-x1+1+y2-y1+1);
    	}
    	sort(a+1,a+1+idx,cmp);
    	build(1,1,2*N+1);
    	for(int i=1;i<=idx;i++){
    		if(a[i].w==1){
    			change(1,1,2*N+1,a[i].xa,1);
    			change(1,1,2*N+1,a[i].xb,1);
    		}
    		ans+=query(1,1,2*N+1,a[i].xa,a[i].xb);
    		if(a[i].w==-1){
    			change(1,1,2*N+1,a[i].xa,-1);
    			change(1,1,2*N+1,a[i].xb,-1);
    		}
    	}
    	cout<<ans<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[b3f091ab046e449296e51bb9005a9f6d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/bd69e1fa543a43b5b5ea0039c9d0af7a.png
[563bbe9d957a46e5b9ec6bac82221d8d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/89047e6218034fa5b91ebbbd5d36357e.png
[cbd17e8a92f5451798c577446e65488f.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/f44c7205839d45e597ce922b184aaad9.png