概述

到现在也只是理解了kaungbin的代码，，，知道每一步做什么，，，但感觉就是哪里有些不对劲的样子，，，，

这道题有两个点是我感觉很重要的，，，一个是数据的离散化，，，另一个是线段树的变形，，，也就是它所维护的东西和之前见过的不一样了，，，，

分析思路

题意是这样的，，，在一个很大的区间里，，，不停的给每一个区间覆盖海报，，，每个覆盖的海报是不一样的，，然后问你最后一共有几个海报是露出来的，，，

大体上的思路是与所给贴海报相反的顺序贴海报，，，这样的话第一张（也就是原来顺序的最后一张）一定是全露出来的，，然后第二张（也就是原来顺序的倒数第二张）如果是在第一张的区间里说明它就被完全覆盖了，，如果是在第一张以外的其他地方，，，就说明这张也一定是露出来的，，，以此类推，，对于每一次判断出是露出来的++ans，，，最终全处理了就得到了答案，，，数据要离散后再用，，，

可以看出这样的写法中线段树只是用来判断每一次的贴海报，，，也就是说，，，线段树只是用来维护每一个区间是否被覆盖（更新），，，同时返回所要覆盖的区间是否有露出来的（查询），，，所以更新和查询的操作可以合并在一起，，，，

实现

数据的离散化

先说一下离散怎么实现:

首先原数据保存到x[maxn]数组，，，

然后把所有的数据复制到另一个数组a[maxn]，，，

对其排序，，，

去重，，，

然后对去重的数组a[maxn]遍历进行离散，，，

这样想要知道知道原来数据中x所对应离散后的位置就为hash[x]，，，

sort(a , a + count);

count = unique(a , a + count) - a;

for(int i = 0; i < count; ++i)

    hash[a[i]] = i;

最后的代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <cstring>

using namespace std;

#define lson rt<<1,l,mid

#define rson rt<<1|1,mid+1,r

const int maxn = 1e5 + 10;

struct node

{

    int l;

    int r;

    bool cov;       //表示这个节点所代表的区间是否被覆盖

}node[maxn << 2];

struct poster       //表示海报的结构体

{

    int l;

    int r;

}poster[maxn << 2];

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

{

    node[rt].l = l;

    node[rt].r = r;

    node[rt].cov = false;   //每一个区间初始化为未覆盖

    if(l == r)  return;

    int mid = (l + r) >> 1;

    build(lson);

    build(rson);

}

bool post(int rt , int l , int r)

{

    //当前节点，所要覆盖的额区间[l , r]

    if(node[rt].cov)    return false;                   //若这个区间已经被覆盖直接返回

    if(node[rt].l == l && node[rt].r == r)

    {

        node[rt].cov = true;                            //未覆盖的前提下找到整个区间时

        return true;

    }

    bool res;

    int mid = (node[rt].l + node[rt].r) >> 1;

    if(r <= mid)    res = post(rt << 1 , l , r);

    else if(l > mid)res = post(rt << 1 | 1 , l , r);

    else

    {

        bool r1 = post(rt << 1 , l , mid);

        bool r2 = post(rt << 1 | 1 , mid + 1 , r);

        res = r1 || r2;                                 //当跨两个区间时，，，要分别判断是否都是被覆盖的，，有一个没覆盖即露出就说明这个区间有露出的

    }

    if(node[rt << 1].cov && node[rt << 1 | 1].cov)      //两个子区间都露出父节点也是露出

        node[rt].cov = true;

    return res;

}

int a[maxn];

int hash[10000010];

int main()

{

    int T;scanf("%d" , &T);

    while(T--)

    {

        int n;

        scanf("%d" , &n);

        int count = 0;

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

        {

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

            a[count++] = poster[i].l;

            a[count++] = poster[i].r;

            //相邻存点

        }

        //离散

        sort(a , a + count);

        count = unique(a , a + count) - a;

        for(int i = 0; i < count; ++i)

            hash[a[i]] = i;

        build(1 , 0 , count - 1);

        int ans = 0;

        for(int i = n - 1; i >= 0; --i)             //反着遍历，，有露出的就增一

            if(post(1 , hash[poster[i].l] , hash[poster[i].r]))

                ++ans;

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

    }

}

//一个缺点，，，这样单纯的离散数据会出错，，，像这一组，，，

//但是poj上没有考虑这种情况，，，，应该是标程的离散也是这样把，，，，，，

//3

//1 10

//1 3

//6 10

//2

//应该是3

总结

暑假时接触过一次数据的离散化，，，但是当时只是会用就行，，，最终还是忘记了，，，只知道这样一个名词，，，这次花了点时间记忆了一下，，，但是还是没有仔细深入的看看，，，因为以前看到的离散化时用的lower_bound()，，，，而且操作更加的复杂，，，过一段时间再看看把，，，，
看到网上好多人用的线段树的结构和之前写的那样一样，，，build(),update(),query()，，，但就是理解不了，，，QAQ，，，看了kuangbin的写法反到理解了，，，虽然基本是照搬过来的，，，，再过几天要重写一遍，，，

(end)

秒客网

poj-2528线段树练习

概述

分析思路

实现

数据的离散化

最后的代码

总结

相关文章