求助扫描线
查看原帖
求助扫描线
160839
Prean楼主2020/8/5 22:24

RT,找了半天没找出来错哪儿了。。。WA20 qaq

求dalao查错/kel

#include<algorithm>
#include<cstdio>
#define DEBUG printf("Baylor AK IOI\n");
const int M=1e5+5;
int n,cnt,x[M<<1],vis[M<<2],len[M<<2];
long long ans;
inline void pushup(int u,int L,int R){
    if(vis[u])len[u]=x[R]-x[L];
    else len[u]=len[u<<1]+len[u<<1|1];
}
void update(int u,int l,int r,int v,int L=1,int R=cnt){
    if(r<=L||R<=l)return;
    if(l<=L&&R<=r){
        vis[u]+=v;
    }
    else if(L<R){
        int mid=L+R>>1;
        update(u<<1,l,r,v,L,mid);
        update(u<<1|1,l,r,v,mid,R);
    }
    pushup(u,L,R);
}
struct LINE{
    int L,R,x,val;
    inline bool operator<(const LINE&a)const{
        return x<a.x;
    }
}le[M<<1];
signed main(){
    int i,x1,y1,x2,y2;
    scanf("%d",&n);
    for(i=1;i<=n;++i){
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        le[++cnt]=(LINE){x1,x2,y1,1};x[cnt]=x1;
        le[++cnt]=(LINE){x1,x2,y2,-1};x[cnt]=x2;
    }
    std::sort(le+1,le+2*n+1);
    std::sort(x+1,x+cnt+1);
    cnt=std::unique(x+1,x+cnt+1)-x-1;
    for(i=1;i<=(n<<1);++i){
        ans+=1ll*len[1]*(le[i].x-le[i-1].x);
        le[i].L=std::lower_bound(x+1,x+cnt+1,le[i].L)-x;
        le[i].R=std::lower_bound(x+1,x+cnt+1,le[i].R)-x;
        update(1,le[i].L,le[i].R,le[i].val);
    }
    printf("%lld\n",ans);
}
2020/8/5 22:24
加载中...