POJ 2528 Mayor's posters（线段树）

 

题目大意

 

贴海报。每张海报的高度都是一样的，唯独宽度不一样。每张海报只能占用整数倍的单位线段长度，贴了 n(n<=10000) 张海报之后，有几张能够看见（有一个角能看见这张海报也算被看见了）？海报的宽度最大可以达到 10^7

 

做法分析

 

一看就是线段树

先不考虑线段的长度能够达到 10^7

肯定是给每张海报一个颜色，然后在这张海报能够占领的区间中涂上这个颜色。每次更新的时候就直接区间操作，记得使用懒操作

最后统计颜色就行了，统计颜色的时候用一个辅助数组，记录这个颜色是否出现过

最后就是处理线段的长度了，显然离散化

但是这里有一个小问题：题目所给的区间，例如是 [2, 4] ，表示的是 第 2 个到第 4 个长度为 1 的小区间。我们这里不能直接根据数的大小离散化

排序后，假设当前数是 x，如果 x-1 出现过，那么 x 离散化后应该是 x-1 的标记 +1，否则应该是上一个的标记 +2

 

参考代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;

const int N=20006;

int ans;
bool vs[N];

struct interval_tree
{
    struct data
    {
        int st, en, color;
        data() {}
        data(int a, int b, int c)
        {
            st=a, en=b, color=c;
        }
    }T[N<<3];

    void build(int id, int L, int R)
    {
        T[id]=data(L, R, 0);
        if(L==R) return;
        int mid=(L+R)>>1;
        build(id<<1, L, mid);
        build(id<<1|1, mid+1, R);
    }

    inline void pushDown(int id)
    {
        T[id<<1].color=T[id<<1|1].color=T[id].color;
        T[id].color=0;
    }

    void update(int id, int L, int R, int color)
    {
        if(L<=T[id].st && T[id].en<=R)
        {
            T[id].color=color;
            return;
        }
        if(T[id].color!=0) pushDown(id);

        int mid=(T[id].st+T[id].en)>>1;
        if(R<=mid) update(id<<1, L, R, color);
        else if(L>mid) update(id<<1|1, L, R, color);
        else update(id<<1, L, R, color), update(id<<1|1, L, R, color);
    }

    void query(int id)
    {
        if(T[id].color!=0 && !vs[T[id].color])
        {
            ans++, vs[T[id].color]=1;
            return;
        }
        if(T[id].st==T[id].en) return;
        if(T[id].color!=0) pushDown(id);
        query(id<<1), query(id<<1|1);
    }
}tree;

vector <int> temp;
map <int, int> ihash;

struct node
{
    int L, R;
    node() {}
    node(int a, int b)
    {
        L=a, R=b;
    }
}op[N];
int n, t, tot;

int main()
{
    scanf("%d", &t);
    for(int ca=1; ca<=t; ca++)
    {
        scanf("%d", &n);
        temp.clear(), ihash.clear(), tot=0;
        for(int i=0, a, b; i<n; i++)
        {
            scanf("%d%d", &a, &b);
            op[i]=node(a, b);
            temp.push_back(a), temp.push_back(b);
        }
        sort(temp.begin(), temp.end());
        for(int i=0; i<2*n; i++)
        {
            int u=temp[i];
            if(ihash.find(u)==ihash.end())
            {
                if(ihash.find(u-1)==ihash.end())
                    ihash.insert(make_pair(u, tot+1)), tot+=2;
                else
                    ihash.insert(make_pair(u, tot)), tot++;
            }
        }

        tree.build(1, 1, tot+2);
        for(int i=0; i<n; i++)
            tree.update(1, ihash[op[i].L], ihash[op[i].R], i+1);
        for(int i=1; i<=n; i++) vs[i]=0;
        ans=0;
        tree.query(1);
        printf("%d\n", ans);
    }
    return 0;
}

AC通道

 

POJ 2528 Mayor's posters

南洋理工 第 9 题 posters