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

不知道為啥，這份代碼從左往右掃會有BUG

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/73554.html

標籤：其他

上一篇：樹狀陣列的基本操作

下一篇：Latex學習體會