扫描线求调(悬赏关注)
  • 板块学术版
  • 楼主Epi4any
  • 当前回复7
  • 已保存回复7
  • 发布时间2023/7/13 09:32
  • 上次更新2023/11/3 10:11:31
查看原帖
扫描线求调(悬赏关注)
374769
Epi4any楼主2023/7/13 09:32

刚刚自学完扫描线,连挂三发心态炸了

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn=1e5+10;
ll n,temp=1,lazy[maxn<<3],ans;
ll X1,X2,Y1,Y2;
double s[maxn<<3];
double min(double x, ll y) {
    return x<y?x:y;
}
double max(double x, ll y) {
    return x>y?x:y;
}
struct Node1{
    double l,r;
    double sum;
} t[maxn<<3];
struct Node2{
    double x,y1,y2;
    ll flag;
} p[maxn<<3];
bool cmp(Node2 a, Node2 b) {
    return a.x < b.x;
}
void pushup(ll rt) {
    if(lazy[rt]>0) {
        t[rt].sum=t[rt].r-t[rt].l;
    }
    else {
        t[rt].sum=t[rt<<1].sum+t[rt<<1|1].sum;
    }
}
void build(ll rt, ll l, ll r) {
    if(r-l>1) {
        t[rt].l=s[l];
        t[rt].r=s[r];
        build(rt*2,l,(l+r)/2);
        build(rt*2|1,(l+r)/2,r);
        pushup(rt);
    }
    else {
        t[rt].l=s[l];
        t[rt].r=s[r];
        t[rt].sum=0;
    }
    return;
}
void update(ll rt, ll y1, ll y2, ll flag) {
    if(t[rt].l==y1 && t[rt].r==y2) {
        lazy[rt]+=flag;
        pushup(rt);
        return;
    } else{
        if(t[rt*2].r>y1) {
            update(rt*2,y1,min(t[rt*2].r,y2),flag);
        }
        if(t[rt*2+1].l<y2) {
            update(rt*2|1,max(t[rt*2+1].l,y1),y2,flag);
        }
        pushup(rt);
    }
}
int main() {
    cin>>n;
    ans=0;
    for(int i=0;i<n;i++) {
        cin>>X1>>Y1>>X2>>Y2;
        p[i].x=X1;
        p[i].y1=Y1;
        p[i].y2=Y2;
        p[i].flag=1;
        p[i+n].x=X2;
        p[i+n].y1=Y1;
        p[i+n].y2=Y2;
        p[i+n].flag=-1;
        s[i+1]=Y1;
        s[i+n+1]=Y2;
    }
    sort(s+1,s+(2*n+1));
    sort(p,p+2*n,cmp);
    build(1,1,2*n);
    memset(lazy,0,sizeof(lazy));
    update(1,p[0].y1,p[0].y2,p[0].flag);
    for(int i=1;i<2*n;i++) {
        ans+=(p[i].x-p[i-1].x)*t[1].sum;
        update(1,p[i].y1,p[i].y2,p[i].flag);
    }
    cout<<ans<<endl;
    return 0;
}
2023/7/13 09:32
加载中...