HDU1828 Picture

痛定思痛。 2023-01-11 09:24 105阅读 0赞

\-----------------------

扫描线求周长

链接（HDU）：[Miku][]

链接（Vjudge）：[Miku][Miku 1]

\-----------------------

HDU是多组数据！！！而且不写明白了！！！

我本以为既然多组数据，何不写上一共几组，既然不写，那必然是不存在了

但是它就是多组数据

\----------------------

这道题显然的做法是扫描两次，横着一次竖着一次，不过会很繁琐

事实上，一次就够了

\-----------------------

完全可以从上向下扫描一次，对于竖线，显然就是两条线段之间的高度\*区间个数\*2（更新前）

而对于横线，就是两次的区间长度之差的绝对值（因为无论是+还是-，裸露出来的就是变化的长度）  
\-------------------------

这样就变成了两个小问题了

横线的求法，没有特别之处，但是竖线，因为是求区间线段数，就要特别处理一下了

我用了额外两个数组，ld，rd，代表一个区间的左右端点是否被覆盖，显然左端点就是左儿子左端点，右端点同理

但是如果左右儿子连起来了，还要特判

所以pushup更长了

void pushup(int x,int l,int r){
        if(lazy[x]>=1){
            sum[x]=r-l+1;
            summ[x]=2;
            ld[x]=rd[x]=1;
            }
        else if(l!=r){
            sum[x]=sum[x<<1]+sum[x<<1|1];
            ld[x]=ld[x<<1];
            rd[x]=rd[x<<1|1];
            summ[x]=summ[x<<1]+summ[x<<1|1];
            if(ld[x<<1|1]&&rd[x<<1]) summ[x]-=2;
            }
        else{
            sum[x]=0;
            summ[x]=0;
            ld[x]=0;
            rd[x]=0;
            }
    }

\---------------------------

这样来看，整个代码也就呼之欲出了

\-----------------------------

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    int xx,yy,xxx,yyy;
    long long ans;
    const int maxn=100000;
    int last;
    struct li{
        int l;
        int r;
        long long  h;
        int f;
    }line[200005];
    int n;
    int p;
    int sum[4000005];
    bool ld[4000005],rd[4000005];
    int lazy[4000005];
    int summ[4000005];
    int lm;
    int rm;
    bool cmp(li x,li y){
        return x.h<y.h;
    }
    void pushup(int x,int l,int r){
        if(lazy[x]>=1){
            sum[x]=r-l+1;
            summ[x]=2;
            ld[x]=rd[x]=1;
            }
        else if(l!=r){
            sum[x]=sum[x<<1]+sum[x<<1|1];
            ld[x]=ld[x<<1];
            rd[x]=rd[x<<1|1];
            summ[x]=summ[x<<1]+summ[x<<1|1];
            if(ld[x<<1|1]&&rd[x<<1]) summ[x]-=2;
            }
        else{
            sum[x]=0;
            summ[x]=0;
            ld[x]=0;
            rd[x]=0;
            }
    }
    void update(int x,int l,int r,int L,int R,int d){
        if(L<=l&&r<=R){
            lazy[x]+=d;
            pushup(x,l,r);
            return ;
        }
        int mid=(l+r)>>1;
        if(L<=mid) update(x<<1,l,mid,L,R,d);
        if(R>mid) update(x<<1|1,mid+1,r,L,R,d);
        pushup(x,l,r);
    }
    int main(){
        while(~scanf("%d",&n)){
            cin>>n;
            p=0;
            ans=0;
            last=0;
            lm=-10000;
            rm=10000;
        for(int i=1;i<=n;++i){
            scanf("%d%d%d%d",&xx,&yy,&xxx,&yyy);
            lm=min(lm,xx);
            rm=max(rm,xxx);
            p++;
            line[p].l=xx;
            line[p].r=xxx;
            line[p].h=yy;
            line[p].f=1;
            p++;
            line[p].l=xx;
            line[p].r=xxx;
            line[p].h=yyy;
            line[p].f=-1;
        }
        sort(line+1,line+p+1,cmp);
        for(int i=1;i<=p;++i){
            update(1,lm,rm-1,line[i].l,line[i].r-1,line[i].f);
            ans+=summ[1]*(line[i+1].h-line[i].h);
            ans+=abs(sum[1]-last);
            last=sum[1];
            }
        cout<<ans;
        }
        return 0;
    }

不知道为啥，这份代码从左往右扫会有BUG

[Miku]: http://acm.hdu.edu.cn/showproblem.php?pid=1828
[Miku 1]: https://vjudge.net/problem/HDU-1828