1. 首页
2. 扫描线
3. 本页

HDU 1828 Picture (扫描线)

题目链接：点我~~

题意：还未更新。。。

思路：还未更新。。。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PI;
typedef pair< PI, int> PII;
const double eps=1e-5;
const double pi=acos(-1.0);
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
#define Key_value ch[ch[root][1]][0]
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int MAXN = 200000+100;
const int MAXM = 200000+100;

int len[MAXN];
int cnt[MAXN];
bool lbd[MAXN],rbd[MAXN];
int num[MAXN];

struct Seg
{
    int l,r,h,f;
    Seg() {}
    Seg(int _l,int _r,int _h,int _f):l(_l),r(_r),h(_h),f(_f) {}
    bool operator <(const Seg &b)const
    {
        if(h==b.h)return f>b.f;
        return h<b.h;
    }
} seg[MAXN];

inline void pushup(int rt,int l,int r)
{
    if(cnt[rt])
    {
        lbd[rt]=rbd[rt]=1;
        len[rt]=r+1-l;
        num[rt]=2;
    }
    else if(l==r)
    {
        len[rt]=lbd[rt]=rbd[rt]=num[rt]=0;
    }
    else
    {
        lbd[rt]=lbd[rt<<1];
        rbd[rt]=rbd[rt<<1|1];
        num[rt]=num[rt<<1]+num[rt<<1|1];
        len[rt]=len[rt<<1]+len[rt<<1|1];
        if(lbd[rt<<1|1] && rbd[rt<<1])
            num[rt]-=2;
    }
}

void modify(int L,int R,int add,int l,int r,int rt)
{
    if(L<=l && r<=R)
    {
        cnt[rt]+=add;
        pushup(rt,l,r);
        return ;
    }
    int m=(l+r)>>1;
    if(L<=m)
        modify(L,R,add,lson);
    if(R>m)
        modify(L,R,add,rson);
    pushup(rt,l,r);
}

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        int x1,y1,x2,y2;
        int k=0;
        int L=INF;
        int R=-INF;
        for(int i=0; i<n; ++i)
        {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            seg[k++]=Seg(x1,x2,y1,1);
            seg[k++]=Seg(x1,x2,y2,-1);
            L=min(L,x1);
            R=max(R,x2);
        }
        sort(seg,seg+k);
        int ans=0,last=0;
        for(int i=0; i<k; ++i)
        {
            modify(seg[i].l,seg[i].r-1,seg[i].f,L,R-1,1);
            ans+=num[1]*(seg[i+1].h-seg[i].h);
            ans+=abs(len[1]-last);
            last=len[1];
        }
        cout<<ans<<endl;
    }

    return 0;
}