HDU1828 Picture-蒲公英云

HDU1828 Picture

-———————————

扫描线求周长

链接（HDU）：Miku

链接（Vjudge）：Miku

-———————————

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;
}