POJ.2528 Mayor’s posters (线段树 区间更新 区间查询 离散化)

题意分析

贴海报，新的海报能覆盖在旧的海报上面，最后贴完了，求问能看见几张海报。

最多有10000张海报，海报左右坐标范围不超过10000000。

一看见10000000肯定就要离散化了，因为建树肯定是建不下。离散化的方法是：先存到一个数组里面，然后sort，之后unique去重，最后查他离散化的坐标lower_bound就行了。特别注意如果是从下标为0开始存储，最后结果要加一。多亏wmr神犇提醒。

这题是覆盖问题。如果正向考虑，后者就可以覆盖在前者之上；如果逆向考虑，就是前者不能涂在后者之上。这里采用逆向考虑的方法。

具体实现细节是，我们按照给出的顺序逆向枚举，将查询和更新一体化，如果按照给出的区间查询到某个地方，发现没有涂色，那说明这张海报一定可以看见，反之不能被看见，根据每次查询的结果，来决定计数器是否自增。

代码总览

#include <cstdio>

#include <cstring>

#include <algorithm>

#define nmax 10005

using namespace std;

struct Tree{

    int l,r;

    //int val;

    bool iscover;

    int mid(){

        return (l+r)>>1;

    }

};

Tree tree[nmax<<4];

struct point{

    int l;

    int r;

}p[nmax<<1];

int finalpos[nmax<<1];

bool flag = false;

int ans = 0;

void PushUp(int rt)

{

    tree[rt].iscover = tree[rt<<1].iscover && tree[rt<<1|1].iscover;

}

void Build(int l, int r, int rt)

{

    tree[rt].l = l; tree[rt].r = r;

    tree[rt].iscover = false;

    if(l == r){

        return;

    }

    Build(l,tree[rt].mid(),rt<<1);

    Build(tree[rt].mid()+1,r,rt<<1|1);

}

void Query(int l,int r,int rt)

{

    if(tree[rt].iscover) return;

    if(l>tree[rt].r || r<tree[rt].l) return ;

    if(tree[rt].l == tree[rt].r){

        if(!tree[rt].iscover){

            tree[rt].iscover = true;

            flag = true;

        }

        return;

    }

    //PushDown(rt);

    //if(l <= tree[rt].l && tree[rt].r <= r) return tree[rt].val;

    Query(l,r,rt<<1) , Query(l,r,rt<<1|1);

    PushUp(rt);

}

int t,n;

int tag = 0;

void discretization()

{

    tag = 0;

    for(int i = 0;i<n;++i){

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

        finalpos[tag++] = p[i].l;

        finalpos[tag++] = p[i].r;

    }

    sort(finalpos,finalpos+tag);

    tag = unique(finalpos,finalpos+tag) - finalpos;

}

int main()

{

    //freopen("in2528.txt","r",stdin);

    scanf("%d",&t);

    while(t--){

        scanf("%d",&n);

        discretization();

        Build(1,nmax<<2,1);

        ans = 0;

        for(int i = n-1; i>=0;--i){

            flag = false;

            int a = lower_bound(finalpos,finalpos+tag,p[i].l) - finalpos+1;

            int b = lower_bound(finalpos,finalpos+tag,p[i].r) - finalpos+1;

            Query(a,b,1);

            if(flag) ans++;

        }

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

    }

    return 0;

}