POJ2528 Mayor's posters【线段树+lazy标志+离散化+hash+折半查找】

简介:
+关注继续查看
Problem: 2528   User: qq1203456195
Memory: 1120K   Time: 94MS
Language:C++   Result: Accepted
复制代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define maxn 11111
int hash[maxn];
int li[maxn],ri[maxn];
int X[maxn<<4];
int col[maxn<<4];//maxn张海报对应maxn<<1个边界,最多需要添加maxn<<1个辅助点,即的线段树要((maxn<<1)<<1)<<2个结点。
int cnt;

void PushDown(int rt)//lazy标志位下传
{
    if(col[rt]!=-1)
    {
        col[rt<<1]=col[rt<<1|1]=col[rt];
        col[rt]=-1;
    }
}

void update(int L,int R,int C,int l,int r,int rt)
{
    int m=(l+r)>>1;
    if(L<=l&&r<=R)
    {
        col[rt]=C;
        return;
    }
    PushDown(rt);
    if (L<=m)    update(L,R,C,lson);
    if (m< R)    update(L,R,C,rson);

}
void query(int l,int r,int rt)
{
    int m=(l+r)>>1;
    if(col[rt]!=-1)
    {
        if(!hash[col[rt]])
            cnt++;
        hash[col[rt]]=1;
        return;
    }
    if(l==r)    return;
    query(lson);
    query(rson);

}
int Bin(int key,int len,int *x)//在长度为len的数组中二分查找key的位置
{
    int l=0,r=len;
    int m;
    while(l<=r)
    {
        m=(l+r)>>1;
        if(x[m]==key)    return m;
        if(x[m]<key)    l=m+1;
        else            r=m-1;
    }
    return -1;
}
int main()
{
    int i,m,n,p,cas,L,R,C;
    scanf("%d",&cas);
    while (cas--)
    {
        scanf("%d",&n);
        //读取数据,并构造待离散化数组X,离散化第一步
        p=0;
        for (i=0;i<n;i++)
        {
            scanf("%d%d",&li[i],&ri[i]);
            X[p++]=li[i];
            X[p++]=ri[i];
        }
        //将X内数据排序,离散化第二步(注意数据范围:x[0]...x[p-1])
        sort(X,X+p);
        //去掉X内重复值,离散化第三步
        /*从1开始,到p-1为止*/
        m=1;
        for (i=1;i<p;i++)
        {
            if(X[i]!=X[i-1])//如果不等,说明没有出现过,就保留;否则就丢弃。
                X[m++]=X[i];
        }
        /*难点!如果出现1,2,5,9这种数据,就改成1,2,5,6,9
        也就是说如果相邻数字间距大于1的话,在其中加上任意一个和相邻数字中的某个数字
        差值为1的数字
        */
        for (i=m-1;i>0;i--)
        {
            if(X[i]!=X[i-1]+1)
                X[m++]=X[i-1]+1;
        }
        sort(X,X+m);//(注意数据范围:x[0]...x[m-1])
        //离散化结束,只需建立叶子节点为m的线段树即可,X[m]的值就是输入的数据中的一个。
        //为了统计海报的个数,就需要海报的标记,而li,ri的下标就可以做海报的标记
        //创建线段树
        memset(col,-1,sizeof(col));
        for (i=0;i<n;i++)
        {
            L=Bin(li[i],m-1,X);
            R=Bin(ri[i],m-1,X);
            C=i;
            update(L,R,C,0,m,1);
        }
        //统计海报个数
        cnt=0;
        memset(hash,0,sizeof(hash));
        query(0,m,1);
        printf("%d\n",cnt);
    }
    return 0;
}
复制代码

 

本文转自ZH奶酪博客园博客,原文链接:http://www.cnblogs.com/CheeseZH/archive/2012/05/11/2496536.html,如需转载请自行联系原作者

相关文章
|
4月前
|
算法 程序员
【牛客算法BM2】 链表内指定区间反转
你好,欢迎来到我的博客!作为一名程序员,我经常刷LeetCode题目来提升自己的编程能力。在我的博客里,我会分享一些我自己做过的题目和解题思路,希望能够帮助到大家。今天,我想和大家分享一道挑战性较高的题目,让我们一起来挑战一下吧!作者也是在学习的过程中刷到有意思的题目就会选择与大家分享,并且提供较优解,关于力扣 的文章全部放在博客,如果大家喜欢记得支持作者。🤓
|
7月前
|
算法
经典算法题---链表奇偶重排(好题)&&双指针系列
经典算法题---链表奇偶重排(好题)&&双指针系列
57 0
经典算法题---链表奇偶重排(好题)&&双指针系列
|
7月前
|
机器学习/深度学习 存储 人工智能
【数组与链表算法】矩阵算法在程序中常见的简单应用 | C++
数组与链表都是相当重要的结构化数据类型,也都是典型线性表的应用。线性表用于计算机中的数据存储结构,按照内存存储的方式基本上可以分为以下两种:静态数据结构和动态数据结构。数组类型就是一种典型的静态数据结构,动态数据结构又称为链表。在我前面的算法系列文章都细致的对二者的使用方法做过讲解。
79 0
【数组与链表算法】矩阵算法在程序中常见的简单应用 | C++
|
7月前
|
算法
算法练习——(8)用下标排序
问题:给你n个无序的int整型数组arr,并且这些整数的取值范围都在0-20之间,要你在 O(n) 的时间复杂度中把这 n 个数按照从小到大的顺序打印出来。
【每日一题Day77】LC1802有界数组中指定下标处的最大值 | 二分查找+贪心
当数组和一定时,要使指定下标处的数值最大,应以该位置为中心,相邻位置以1为间隔梯度下降,直至数值等于1【贪心获得数组和】
|
9月前
CF960F. Pathwalks (树上二维LIS 线段树 动态开点树状数组)
CF960F. Pathwalks (树上二维LIS 线段树 动态开点树状数组)
|
11月前
|
算法 索引
【Day28】力扣算法(超详细思路+注释) [1790. 仅执行一次字符串交换能否使两个字符串相等 ] [328. 奇偶链表 ][148. 排序链表]
了解(超详细思路+注释) [1790. 仅执行一次字符串交换能否使两个字符串相等 ] [328. 奇偶链表 ][148. 排序链表]。
62 0
【Day28】力扣算法(超详细思路+注释) [1790. 仅执行一次字符串交换能否使两个字符串相等 ] [328. 奇偶链表 ][148. 排序链表]
|
11月前
|
算法 测试技术
【Day27】 LeetCode算法刷题(思路+注释)[801. 使序列递增的最小交换次数 ]
了解算法刷题(思路+注释)[801. 使序列递增的最小交换次数 ]。
65 0
【Day27】 LeetCode算法刷题(思路+注释)[801. 使序列递增的最小交换次数 ]
|
11月前
|
算法 搜索推荐
【算法专题】秒懂如何运用二分查找算法
【算法专题】秒懂如何运用二分查找算法
【算法专题】秒懂如何运用二分查找算法
AcWing 36. 合并两个排序的链表
AcWing 36. 合并两个排序的链表
88 0
AcWing 36. 合并两个排序的链表
相关产品
云迁移中心
推荐文章
更多