D - Mayor's posters - 2528（区间覆盖）

题意：贴海报

有一面很长的墙，大概有10000000 这么长，现有有一些海报会贴在墙上，当然贴海报的顺序是有先后的，问你当最后一张海报也贴上的时候能不能求出来在这面墙上能看到多少张不同的海报？

分析：因为后面贴的海报会把前面贴的覆盖掉，不太容易求出来，但是如果从最后一张倒着贴，只要判断墙上这段区间有没有被完全覆盖就可以了，因为墙比较长，所以需要离散化一下。

************************************************************************

注意：在向上跟新的时候返回值要在更新的下面要不直接返回了怎么更新？？

#include<stdio.h>

#include<math.h>

#include<string.h>

#include<algorithm>

using namespace std;

const int maxn = 40005;

int Hash[maxn];//记录离散化后的数据

struct Post{int l, r;}p[maxn];//记录海报

struct Tree

{

    int L, R;

    bool isCover;//记录这段区间是否被覆盖

    int Mid(){return (L+R)/2;}

}tree[maxn*4];

void Up(int root)//向上更新，如果左右子树都被覆盖，那么他也会被覆盖

{

    if(tree[root].L != tree[root].R)

    if(tree[root<<1].isCover && tree[root<<1|1].isCover)

        tree[root].isCover = true;

}

void Build(int root, int L, int R)

{

    tree[root].L = L, tree[root].R = R;

    tree[root].isCover = false;

    if(L == R)return ;

    Build(root<<1, L, tree[root].Mid());

    Build(root<<1|1, tree[root].Mid()+1, R);

}

//如果区间能内还有位置返回真，否则返回假

bool Insert(int root, int L, int R)

{

    if(tree[root].isCover)return false;

    if(tree[root].L == L && tree[root].R == R)

    {

        tree[root].isCover = true;

        return true;

    }

    

    bool ans;

    if(R <= tree[root].Mid())

        ans =  Insert(root<<1, L, R);

    else if(L > tree[root].Mid())

        ans =  Insert(root<<1|1, L, R);

    else

    {

        bool Lson = Insert(root<<1, L, tree[root].Mid());

        bool Rson = Insert(root<<1|1, tree[root].Mid()+1, R);

        ans = Lson | Rson;

    }

    Up(root);

    return ans;

}

int main()

{

    int T;

    scanf("%d", &T);

    while(T--)

    {

        int i, N, nh=0;

        scanf("%d", &N);

        for(i=1; i<=N; i++)

        {

            scanf("%d%d", &p[i].l, &p[i].r);

            Hash[nh++] = p[i].l, Hash[nh++] = p[i].l-1;

            Hash[nh++] = p[i].r, Hash[nh++] = p[i].r+1;

        }

        sort(Hash, Hash+nh);

        nh = unique(Hash, Hash+nh) - Hash;

        Build(1, 1, nh);

        int ans = 0;

        for(i=N; i>0; i--)

        {

            int l = lower_bound(Hash, Hash+nh, p[i].l) - Hash;

            int r = lower_bound(Hash, Hash+nh, p[i].r) - Hash;

            if(Insert(1, l, r) == true)

                ans += 1;

        }

        printf("%d\n", ans);

    }

    return 0;

}

巴特西

D - Mayor's posters - 2528（区间覆盖）

最新文章

热门文章