Mayor's posters---poj2528线段树、离散化

题意：有n张海报要贴，每张需要用的区间为L到R，后面的可以贴在之前的上面，就是吧之前的挡住，求最后我们能看到几张海报；

我们可以倒着处理，因为最后贴的我们是能看到的；如果区间被贴过了result不加，没有贴过就+1并标记一下；

由于数据范围太大所以用线段树

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std;

#define N 10100
#define Lson r<<1
#define Rson r<<1|1

struct Post
{
    int L,R;
}p[N];

struct SegTree
{
    int L, R, isCover;
    int Mid()
    {
        return (L+R)/2;
    }
}a[N*16];

int Hash[4*N];

void Up(int r)
{
    if(a[r].L!=a[r].R)
        if(a[Lson].isCover==1 && a[Rson].isCover==1)//向上更新，如果左右子树都被覆盖，那么他也会被覆盖
            a[r].isCover = 1;
}

void BuildSegTree(int r, int L, int R)
{
    a[r].isCover = 0;
    a[r].L = L; a[r].R = R;
    if(L == R)
        return ;
    BuildSegTree(Lson, L, a[r].Mid());
    BuildSegTree(Rson, a[r].Mid()+1, R);
}
int judge(int r, int L, int R)
{
    if(a[r].isCover==1)
        return 0;//被覆盖返回0；
    if(a[r].R == R && a[r].L == L)
    {
        a[r].isCover = 1;
        return 1;
    }
    int ans;
    if(L>a[r].Mid())
        ans = judge(Rson, L, R);
    else if(R<=a[r].Mid())
        ans = judge(Lson, L, R);
    else
    {
        int ans1 = judge(Lson, L, a[r].Mid());
        int ans2 = judge(Rson, a[r].Mid()+1, R);
        ans = ans1 | ans2;//只要有一个没被覆盖就说明能贴；
    }
    Up(r);
    return ans;
}
int main()
{
    int T, n, k;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        k=0;
        for(int i=1; i<=n; i++)
        {
            scanf("%d%d", &p[i].L, &p[i].R);
            Hash[k++]=p[i].L-1;//防止出现离散化后原本不相邻的数变成相邻的了
            Hash[k++]=p[i].L;
            Hash[k++]=p[i].R+1;
            Hash[k++]=p[i].R;
        }
        sort(Hash, Hash+k);
        int len = unique(Hash, Hash+k) - Hash;
        BuildSegTree(1, 1, len);
        int result = 0;
        for(int i=n; i>0; i--)
        {
            int L = lower_bound(Hash, Hash+len, p[i].L) - Hash;
            int R = lower_bound(Hash, Hash+len, p[i].R) - Hash;

            int ans=judge(1, L, R);
            if(ans == 1)
                result++;
        }
        printf("%d
", result);
    }
    return 0;
}

View Code

过了那么久再写一遍

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stack>
using namespace std;

#define INF 0xfffffff
#define N 100050
#define Lson r<<1
#define Rson r<<1|1

struct SegmentTree
{
    int L, R;
    bool IsCover;///判断此区间是否被覆盖；

    int Mid() { return (L+R)>>1;}
    int len() { return R-L+1; }

} a[N<<2];

void Build(int r, int L, int R)
{
    a[r].L = L, a[r].R = R;
    a[r].IsCover = false;

    if(L == R) return;

    Build(Lson, L, a[r].Mid());
    Build(Rson, a[r].Mid()+1, R);

    a[r].IsCover = a[Lson].IsCover && a[Rson].IsCover;
}

int Query(int r, int L, int R)
{
    int ans;
    if(a[r].IsCover == true)
        a[Lson].IsCover = a[Rson].IsCover = a[r].IsCover;

    if(a[r].IsCover == true)///被覆盖了，返回0；
        return 0;
    if(a[r].L == L && a[r].R == R)///没被覆盖，把它覆盖，并返回1；
    {
        a[r].IsCover = true;
        return 1;
    }

    if(R<=a[r].Mid())
        ans = Query(Lson, L, R);
    else if(L>a[r].Mid())
        ans = Query(Rson, L, R);
    else
    {
        int ans1 = Query(Lson, L, a[r].Mid());
        int ans2 = Query(Rson, a[r].Mid()+1, R);
        ans =  (ans1 || ans2);///只要有一边没被覆盖就说明能贴；
    }
    a[r].IsCover = a[Lson].IsCover && a[Rson].IsCover;///向上更新，因为有了这个更新所以不能在上面直接返回结果；
    return ans;
}

struct node
{
    int L, R;
}p[N];

int Hash[N*4], cnt;

int main()
{
    int T, n,  L, R;
    scanf("%d", &T);
    while(T--)
    {
        cnt = 0;
        scanf("%d", &n);
        for(int i=1; i<=n; i++)
        {
            scanf("%d %d", &p[i].L, &p[i].R);
            Hash[cnt++] = p[i].L;   Hash[cnt++] = p[i].R;
            Hash[cnt++] = p[i].L-1; Hash[cnt++] = p[i].R+1;
            ///加上左右边界是为了防止出现本身没有相连的，而离散化之后相连的情况；
        }
        sort(Hash, Hash+cnt);
        cnt = unique(Hash, Hash+cnt)-Hash;

        Build(1, 1, cnt);

        int ans = 0;

        for(int i=n; i>=1; i--)
        {
            L = lower_bound(Hash, Hash+cnt, p[i].L) - Hash;
            R = lower_bound(Hash, Hash+cnt, p[i].R) - Hash;
            ans += Query(1, L, R);
        }
        printf("%d
", ans);
    }
    return 0;
}

View Code