90 分 WA on #11 求助
查看原帖
90 分 WA on #11 求助
350558
_wsq_楼主2024/7/29 21:54
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 100005
#define int long long
struct line{
    int x1,x2,y,val;
    bool operator<(const line &rhs)const{
        return y<rhs.y;
    }
}li[maxn<<1];
int n,num[maxn<<1],sum[maxn<<4],len[maxn<<4],ans;
void pushup(int l,int r,int root){
    if(sum[root]){
        len[root]=num[r+1]-num[l];
    }
    else{
        len[root]=len[root<<1]+len[(root<<1)|1];
    }
    return;
}
void change(int x,int y,int val,int l,int r,int root){
    if(x<=l&&r<=y){
        sum[root]+=val;
        pushup(l,r,root);
        return;
    }
    int mid=(l+r)>>1;
    if(mid>=x){
        change(x,y,val,l,mid,root<<1);
    }
    if(mid<y){
        change(x,y,val,mid+1,r,(root<<1)|1);
    }
    pushup(l,r,root);
    return;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n;i++){
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        li[(i<<1)-1].x1=x1;
        li[(i<<1)-1].x2=x2;
        li[(i<<1)-1].y=y1;
        li[(i<<1)-1].val=1;
        li[i<<1].x1=x1;
        li[i<<1].x2=x2;
        li[i<<1].y=y2;
        li[i<<1].val=-1;
        num[(i<<1)-1]=x1;
        num[i<<1]=x2;
    }
    sort(num+1,num+(n<<1)+1);
    num[0]=unique(num+1,num+(n<<1)+1)-num-1;
    sort(li+1,li+(n<<1)+1);
    for(int i=1;i<(n<<1);i++){
        change(lower_bound(num+1,num+num[0]+1,li[i].x1)-num,lower_bound(num+1,num+num[0]+1,li[i].x2-1)-num-1,li[i].val,1,num[0]-1,1);
        ans+=len[1]*(li[i+1].y-li[i].y);
    }
    cout<<ans;
    return 0;
}
2024/7/29 21:54
加载中...