求调扫描线板子
查看原帖
求调扫描线板子
704275
无名之雾楼主2024/12/18 17:57
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline void write(int x){
    if(x==0){putchar('0');return;}
    int len=0,k1=x,c[10005];
    if(k1<0)k1=-k1,putchar('-');
    while(k1)c[len++]=k1%10+'0',k1/=10;
    while(len--)putchar(c[len]);
}
const int N=1e5+5;
struct node{
    int x1,x2,y,o;
    bool operator <(const node &x){return y<x.y;}
}b[N<<1];
int a[N<<1],v[N<<3],w[N<<3];
struct SGT{
    int ls(int p){return p<<1;}
    int rs(int p){return p<<1|1;}
    void push_up(int p,int pl,int pr){
        if(v[p])w[p]=a[pr]-a[pl];
        else if(pl+1==pr)w[p]=0;
        else w[p]=w[ls(p)+1]+w[rs(p)+1];
    }
    void add(int l,int r,int d,int p,int pl,int pr){
        if(l<=pl&&r>=pr){v[p]+=d;push_up(p,pl,pr);return ;}
        int mid=pl+pr>>1;
        if(l<=mid)add(l,r,d,ls(p)+1,pl,mid);
        if(r>mid)add(l,r,d,rs(p)+1,mid+1,pr);
        push_up(p,pl,pr);
    }
}sgt;
int f(int y,int tot){return lower_bound(a,a+tot,y)-a;}
signed main(){
    int n=read(),cnt=1;
    for(int i=0;i<n;i++){
        int x1=read(),y1=read(),x2=read(),y2=read();
        b[i]={x1,x2,y1,1},b[i+n]={x1,x2,y2,-1};
        a[i]=x1,a[i+n]=x2;
    }
    sort(a,a+n*2);sort(b,b+n*2);
    for(int i=1;i<n*2;i++){
        if(a[i]!=a[cnt-1])a[cnt++]=a[i];
    }
    int sum=0;
    sgt.add(f(b[0].x1,cnt),f(b[0].x2,cnt),1,0,0,cnt-1);
    // cout<<w[0]<<"\n";
    for(int i=1;i<n*2;i++){
        int x1=f(b[i].x1,cnt),x2=f(b[i].x2,cnt);
        sum+=(b[i].y-b[i-1].y)*w[0];
        // cout<<sum<<" ";
        sgt.add(x1,x2,b[i].o,0,0,cnt-1);
    }
    cout<<"\n"<<sum;
    return 0;
}
2024/12/18 17:57
加载中...