18分代码求调
查看原帖
18分代码求调
745048
RadonS楼主2024/11/4 19:37

#include <bits/stdc++.h>
using namespace std;
namespace Radon{
    void Main();
}
int main(){
    Radon::Main();
    return 0;
}

namespace Radon{
    #define int long long
    #define N 100010
    #define ls x<<1
    #define rs x<<1|1
    map<int,int>p;

    struct node{
        int x1,x2,y,opt;
    }a[N<<2];
    bool cmp(node a,node b){
        return a.y<b.y;
    }


    int n,X[N<<2];
    long long ans=0;
    int t[N<<4],len[N<<4],cnt[N<<4];
    void add(int x,int l,int r,int L,int R,int num){
        if(l>=L && r<=R){
            cnt[x]+=num;
            if(cnt[x]==0){
                len[x]=len[ls]+len[rs];
            }else{
                len[x]=X[r+1]-X[l];
            }
            return;
        }
        int mid=(l+r)>>1;
        if(mid>=L){
            add(ls,l,mid,L,R,num);
        }
        if(mid<R){
            add(rs,mid+1,r,L,R,num);
        }
        int qqew=0;
        if(cnt[x]==0){
            qqew=1;
            if(l==r){
                len[x]=0;
            }else{
                len[x]=len[ls]+len[rs];
            }
        }else{
            qqew=2;
            len[x]=X[r+1]-X[l];
        }
        return;
    }



    int find(int x){
        return lower_bound(X+1,X+1+n,x)-X;
    }


    void Main(){
        // freopen("P5490_3.in","r",stdin);
        // freopen("P5490.out","w",stdout);
        ios::sync_with_stdio(0);
        cin.tie(0);cout.tie(0);
        cin >> n;
        for(int x=1;x<=n;x++){
            int x1,x2,y1,y2;
            cin >> x1 >> y1 >> x2 >> y2;
            a[x*2-1]={x1,x2,y1,1};
            a[x*2]={x1,x2,y2,-1};
            X[x*2-1]=x1;
            X[x*2]=x2;
        }
        n<<=1;
        sort(a+1,a+1+n,cmp);
        sort(X+1,X+1+n);
        int nnum;
        nnum=unique(X+1,X+1+n)-X-1;
        add(1,1,nnum-1,find(a[1].x1),find(a[1].x2)-1,a[1].opt);
        for(int x=2;x<=n;x++){
            int y2=a[x].y,y1=a[x-1].y;
            ans+=(y2-y1)*len[1];
            add(1,1,nnum-1,find(a[x].x1),find(a[x].x2)-1,a[x].opt);
        }
        cout << ans;
    }
}

2024/11/4 19:37
加载中...