80pts求助WA后两问
查看原帖
80pts求助WA后两问
1517143
Psy_Chen楼主2024/11/28 20:55
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXNUM = 1005;
ll num[2*MAXNUM]={0};

inline int ls(int x){
    return (x*2);
}
inline int rs(int x){
    return (x*2)+1;
}

struct RECTS{
    ll x1,y1,y2;
    int k;
    int y1c,y2c;
}rect[MAXNUM*4];

struct NODES{
    int l,r;
    ll val=0;
    int flag=0;
}node[MAXNUM*8];


void build(int p,int l,int r){
    node[p].l=l,node[p].r=r;
    if(l==r) return;
    int m =(l+r)/2;
    build(ls(p),l,m);build(rs(p),m+1,r);
    return;
}

void pushup(int p){
    int l=node[p].l,r=node[p].r;
    if(node[p].flag!=0) node[p].val=num[r+1]-num[l];
    else node[p].val=node[ls(p)].val+node[rs(p)].val;  
    return ;
}

void modify(int p,int l,int r,int k){
    int nl=node[p].l,nr=node[p].r;
    if(nr<l||nl>r) return;
    if(l<=nl&&nr<=r){
        node[p].flag+=k;
        pushup(p);
        return;
    }
    modify(ls(p),l,r,k);
    modify(rs(p),l,r,k);
    pushup(p);
    return ;
}



int main(){
    ios::sync_with_stdio(false);
    freopen("P1884_9.in","r",stdin);
    int n;
    long long ans=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {   
        int x1,x2,y1,y2;
        cin>>x1>>y1>>x2>>y2;
        rect[i].x1=x1,rect[i].y1=y1,rect[i].y2=y2,rect[i].k=1;
        rect[i+n].x1=x2,rect[i+n].y1=y1,rect[i+n].y2=y2,rect[i+n].k=-1;
        num[i]=y1,num[i+n]=y2;
    }
    sort(rect+1,rect+1+2*n,[](RECTS a,RECTS b){
        return a.x1<b.x1;
    });
    sort(num+1,num+1+2*n);
    int len = unique(num+1,num+1+2*n)-(num+1);
    build(1,1,len-1);
    for(int i=1;i<=2*n;i++){
        int l=lower_bound(num+1,num+len,rect[i].y1)-num;
        int r=lower_bound(num+1,num+len,rect[i].y2)-num;
        
        modify(1,min(l,r),max(l,r)-1,rect[i].k);
        // ans+=(rect[i+1].x1-rect[i].x1);
        ans+=(rect[i+1].x1-rect[i].x1)*node[1].val;
        if(i==260) 
        cerr<<"Oops!"<<endl;
    }
    cout<<ans<<endl;
    return 0;
}
2024/11/28 20:55
加载中...