poj_2528 Mayor's posters （线段树经典题+离散化方法）

由于题面中给定的wall最大长度为10 000 000；若简单用线段树势必会超时。

而注意到题面中规定了输入海报的个数<=1000；因此不妨离散化，使得线段中叶节点仅含有1000个，那么线段最大深度为10，不会TLE。

同时在构造线段树的时候除了设置基本的长度变量l,r之外，

设置了一个新的变量kind用于储存当前线段的覆盖状态（=0表示没有覆盖或有多个覆盖；=1表示只有一个覆盖）。这样当计算最终状态时只需要对遍历到的每一个kind不为0的线段计数值加1。同时线段的搜索也在这里终止（因为若上层线段已经覆盖，那么下层必然也被覆盖，因而不需重复搜索）。

这是本题解题的关键，也是体现线段树结构特色的地方，值得好好品味，很轻巧的构造。

此外在解题中出现了两次bug：

1、sort()范围出错，由于是从1位置开始而非0位置，因此范围需要+1；

2、使用map报TLE，改为int数组后AC。

AC代码如下：

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<map>

#include<cstring>

#include<algorithm>

using namespace std;

//代码原本使用map来记录位置和编号的映射，但是TLE；改成int数组后就ac了。stl还是要慎用。

//编程思路:先想清楚算法，先实现数据结构,再写主函数

const int maxn=+;

struct line{

    int l,r,kind;//这个kind的记录是精华

}tree[maxn*];//这个数量的判定 （1000的叶子，最多10层，取最大值10*maxn）

int l[maxn],r[maxn];

int poster[maxn*];//记录海报的所有坐标,离散化 

void build(int l,int r,int node){

    tree[node].l=l,tree[node].r=r;

    if(l==r)return;

    int mid=(l+r)/;

    build(l,mid,node*);

    build(mid+,r,node*+);

}

void update(int l,int r,int node,int k){

    if(tree[node].l==l&&tree[node].r==r){

        tree[node].kind=k;//完全覆盖

        return;

    }

    if(tree[node].kind==k)return ;

//    if(tree[node].kind!=0){//这里的细微差别个人感觉没啥影响（包括上面一行是否有必要存在的问题）

    if(tree[node].kind!=&&tree[node].kind!=k){

        tree[node*].kind=tree[node].kind;

        tree[node*+].kind=tree[node].kind;

        tree[node].kind=;

    }

    if(r<=tree[node*].r){

        update(l,r,node*,k);

    }

    else if(l>=tree[node*+].l){

        update(l,r,node*+,k);

    }

    else{

        update(l,tree[node*].r,node*,k);

        update(tree[node*+].l,r,node*+,k);

    }

}

int result=;

bool flag[maxn];

void cal(int node){

    if(tree[node].kind!=){

        if(flag[tree[node].kind]==false){

            result++;

        //    cout<<tree[node].l<<" "<<tree[node].r<<" "<<tree[node].kind<<endl;//test

            flag[tree[node].kind]=true;

        }

    }

    else{

        cal(node*);

        cal(node*+);

    }

}

int pos2no[] ;

int main(void){

    int t;

    scanf("%d",&t);

    while(t--){

        memset(tree,,sizeof(tree));

        memset(flag,false,sizeof(flag));

        memset(poster,,sizeof(poster));

        memset(pos2no,,sizeof(pos2no));

        int n;

        scanf("%d",&n);

        int j=;

        for(int i=;i<=n;i++){//从1开始编号

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

            poster[++j]=l[i];poster[++j]=r[i];

        }

        sort(poster+,poster+j+);//排序去重 ;注意为什么是j+1 （wa点）

        int len=j,k=;

        for(int i=;i<=len;i++,k++){

            poster[k]=poster[i];

            while(poster[i]==poster[i+])i++;

        }

        int finlen=k-;

        //map<int,int> pos2no;//位置到编号的映射 若使用map也是正确的，但是会报TLE，故弃之。 

        for(int i=;i<=finlen;i++){

            pos2no[poster[i]]=i;

        }

        build(,finlen,) ;

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

            update(pos2no[l[i]],pos2no[r[i]],,i);

        }

        result=;

        cal();

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

    }

    return ;

}

巴特西

poj_2528 Mayor's posters （线段树经典题+离散化方法）

最新文章

热门文章