P5490 扫描线 求调
  • 板块学术版
  • 楼主_dbq_
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/7/23 18:55
  • 上次更新2024/7/23 20:08:06
查看原帖
P5490 扫描线 求调
551134
_dbq_楼主2024/7/23 18:55

rt

#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<string>
#include<stdlib.h>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#define LL long long
#define ULL unsigned long long
#define cint const int 
using namespace std;
cint INTINF=0x7f7f7f7f;
const LL LLINF=9e18;
cint N=1e5+10;
struct node1{
    int h;//高度
    int l,r;//左右坐标
    int f;//f=1表示下边,f=-1表示上边
    friend bool operator<(const node1 &p,const node1 &q){
        return p.h<q.h;
    }
}line[N<<1];//存边
struct node2{
    int l,r;
    int sum;
}d[N<<3];
int lazy[N<<3];
int s[N<<1];
int tmpl,tmps;
LL ans;
inline LL read(){
    LL x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-'){
            f=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
void write(LL x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9){
        write(x/10);
    }
    putchar(x%10+'0');
    return ;
}
void pushup(cint p){
    if(lazy[p]>0){
        d[p].sum=d[p].r-d[p].l;
    }
    else{
        d[p].sum=d[p<<1].sum+d[p<<1|1].sum;
    }
    return ;
}
void build(cint l,cint r,cint p){
    if(r-l>1)
    {
        d[p].l=s[l];
        d[p].r=s[r];
        cint m=l+((r-l)>>1);
        build(l,m,p<<1);
        build(m,r,p<<1|1);
        pushup(p);
    }
    else{
        d[p]={s[l],s[r],0};
    }
    return ;
}
void update(cint l,cint r,cint f,cint p){
    if(d[p].l==l&&d[p].r==r){
        lazy[p]+=f;
        pushup(p);
        return ;
    }
    if(d[p<<1].r>l) update(l,min(d[p<<1].r,r),f,p<<1);
    if(d[p<<1|1].l<r) update(max(d[p<<1|1].l,l),r,f,p<<1|1);
    pushup(p);
    return ;
}
int main()
{
    #ifdef dbq
    freopen("P5490.in","r",stdin);
    freopen("P5490.out","w",stdout);
    #endif
    cint n=read();
    for(int i=1;i<=n;i++)
    {
        int a=read(),b=read(),c=read(),d=read();
        if(a>c) swap(a,c);
        if(b>d) swap(b,d);
        /*
            a=x1=左端点
            b=y1=下边高度
            c=x2=右端点
            d=y2=上边高度
        */
       line[++tmpl]={d,a,c,-1};
       line[++tmpl]={b,a,c,1};
       s[++tmps]=a;
       s[++tmps]=c;
    }
    sort(s+1,s+1+tmps);
    sort(line+1,line+1+tmpl);
    memset(lazy,0,sizeof(lazy));
    build(1,2*n,1);
    update(line[1].l,line[1].r,line[1].f,1);
    for(int i=2;i<=tmpl;i++)
    {
        ans+=(line[i].h-line[i-1].h)*d[1].sum;
        update(line[i].l,line[i].r,line[i].f,1);
    }
    write(ans);
    return 0;
}
2024/7/23 18:55
加载中...