POJ 2528-Mayor's posters(线段树+离散化)_mayor's posters openj_bailian - 2528-程序员宅基地

技术标签: 线段树  ACM  ACM_线段树  

Mayor's posters
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 73717   Accepted: 21263

Description

The citizens of Bytetown, AB, could not stand that the candidates in the mayoral election campaign have been placing their electoral posters at all places at their whim. The city council has finally decided to build an electoral wall for placing the posters and introduce the following rules:
  • Every candidate can place exactly one poster on the wall.
  • All posters are of the same height equal to the height of the wall; the width of a poster can be any integer number of bytes (byte is the unit of length in Bytetown).
  • The wall is divided into segments and the width of each segment is one byte.
  • Each poster must completely cover a contiguous number of wall segments.

They have built a wall 10000000 bytes long (such that there is enough place for all candidates). When the electoral campaign was restarted, the candidates were placing their posters on the wall and their posters differed widely in width. Moreover, the candidates started placing their posters on wall segments already occupied by other posters. Everyone in Bytetown was curious whose posters will be visible (entirely or in part) on the last day before elections.
Your task is to find the number of visible posters when all the posters are placed given the information about posters' size, their place and order of placement on the electoral wall.

Input

The first line of input contains a number c giving the number of cases that follow. The first line of data for a single case contains number 1 <= n <= 10000. The subsequent n lines describe the posters in the order in which they were placed. The i-th line among the n lines contains two integer numbers l i and ri which are the number of the wall segment occupied by the left end and the right end of the i-th poster, respectively. We know that for each 1 <= i <= n, 1 <= l i <= ri <= 10000000. After the i-th poster is placed, it entirely covers all wall segments numbered l i, l i+1 ,... , ri.

Output

For each input data set print the number of visible posters after all the posters are placed.

The picture below illustrates the case of the sample input.

Sample Input

1
5
1 4
2 6
8 10
3 4
7 10

Sample Output

4

Source

题目大意:一面墙给你贴广告,求在最后能看到的广告总数。

解题思路:线段树的区间更新,最后求出出广告的种类即可,主要题目给的区间范围太大,我们要对区间进行离散化一下(就是缩小一下区间跨度)。
在离散化的的时候对于区间的 宽度大于2的中间需要插一个点进去,避免区间覆盖出错!例如:下图的三个区间

AC代码:
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<queue>
#include<map>
#include<set>
#define bug printf("*********\n");
#define mem0(a) memset(a, 0, sizeof(a));
#define mem1(a) memset(a, -1, sizeofa());
#define in1(a) scanf("%d" ,&a);
#define in2(a, b) scanf("%d%d", &a, &b);
#define out1(n) printf("%d\n", n);
using namespace std;
typedef pair<long long, int> par;
const int mod = 1e9+7;
const int INF = 1e9+7;
const int N = 1000010;
const double pi = 3.1415926;

int T, n;
int x[10010], y[10010], a[40010], b[40010], vis[40010];
char str[10];

struct node
{
    int l;
    int r;
    int lazy;
    int num;
}e[40010*4];

void push(int k)
{
    if(e[k].lazy) {
        e[2*k].num = e[k].lazy;
        e[2*k+1].num  = e[k].lazy;
        e[2*k].lazy = e[k].lazy;
        e[2*k+1].lazy = e[k].lazy;
        e[k].lazy = 0;
    }
}

void build(int l, int r, int k)
{
    e[k].l = l;
    e[k].r = r;
    e[k].lazy = 0;
    if(l == r) {
        e[k].num = 0;
        return;
    }
    int mid = (l+r)/2;
    build(l, mid, 2*k);
    build(mid+1, r, 2*k+1);
}

void updata(int l ,int r, int add, int k)
{
    if(l == e[k].l && r == e[k].r) {
        e[k].num = add;
        e[k].lazy = add;
        return;
    }
    push(k);
    int mid = (e[k].l+e[k].r)/2;
    if(r <= mid) updata(l, r, add, 2*k);
    else if(l >= mid+1) updata(l, r, add, 2*k+1);
    else {
        updata(l ,mid, add, 2*k);
        updata(mid+1, r, add, 2*k+1);
    }
}

int quary(int l, int r, int k)
{
    if(e[k].l == l && e[k].r == r) {
        return e[k].num;
    }
    push(k);
    int mid = (e[k].l + e[k].r)/2;
    if(r <= mid) return quary(l ,r, 2*k);
    else if(l+1 >= mid) return quary(l, r, 2*k+1);
}

int main()
{
    in1(T);
    while(T --) {
        in1(n);
        int k = 0, ans = 0;
        mem0(vis);
        for(int i = 0; i < n; i ++) {
            in2(x[i], y[i]);
            a[k ++] = x[i];
            a[k ++] = y[i];
        }
        sort(a, a+k);
        int s = 1;
        b[0] = a[0];
        //离散化坐标
        for(int i = 1; i < k; i ++) {
            if(a[i] != a[i-1]) {
                b[s ++] = a[i];
                if(a[i] - a[i-1] >= 2)
                    b[s ++] = a[i-1]+1;
            }
        }
        sort(b, b+s);
        build(1, s, 1);
        k = 1;
        for(int i = 0; i < n; i ++) {
            int l = upper_bound(b, b+s, x[i]) - b; //查找角标(也就是新的区间跨度)
            int r = upper_bound(b, b+s, y[i]) - b;
            updata(l, r, k++, 1);
        }
        for(int i = 1; i <= s; i ++) { //查找广告种类
            if(!vis[quary(i, i, 1)] && quary(i, i, 1)) {
                ans ++;
                vis[quary(i, i, 1)] = 1;
            }
        }
        out1(ans);
    }
    return 0;
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/I_believe_CWJ/article/details/80284801

智能推荐

python中文显示不出来_解决Python词云库wordcloud不显示中文的问题-程序员宅基地

文章浏览阅读2.6k次。解决Python词云库wordcloud不显示中文的问题2018-11-25背景:wordcloud是基于Python开发的词云生成库,功能强大使用简单。github地址:https://github.com/amueller/word_cloudwordcloud默认是不支持显示中文的,中文会被显示成方框。安装:安装命令:pip install wordcloud解决:经过测试发现不支持显示中文..._词云python代码无法输出文字

台式计算机cpu允许温度,玩游戏cpu温度多少正常(台式电脑夏季CPU一般温度多少)...-程序员宅基地

文章浏览阅读1.1w次。随着炎热夏季的到来,当玩游戏正爽的时候,电脑突然死机了,自动关机了,是不是有想给主机一脚的冲动呢?这个很大的原因是因为CPU温度过高导致的。很多新手玩家可能都有一个疑虑,cpu温度多少以下正常?有些说是60,有些说是70,到底多高CPU温度不会死机呢?首先我们先看看如何查看CPU的温度。下载鲁大师并安装,运行鲁大师软件,即可进入软件界面,并点击温度管理,即可看到电脑各个硬件的温度。鲁大师一般情况下..._台式机玩游戏温度多少正常

小白自学Python日记 Day2-打印打印打印!_puthon打印任务收获-程序员宅基地

文章浏览阅读243次。Day2-打印打印打印!我终于更新了!(哭腔)一、 最简单的打印最最简单的打印语句: print(“打印内容”)注意:python是全英的,符号记得是半角下面是我写的例子:然后进入power shell ,注意:你需要使用cd来进入你保存的例子的文件夹,保存时名字应该取为xxx.py我终于知道为什么文件夹取名都建议取英文了,因为进入的时候是真的很麻烦!如果你没有进入正确的文件夹..._puthon打印任务收获

Docker安装:Errors during downloading metadata for repository ‘appstream‘:_"cenerrors during download metadata for repository-程序员宅基地

文章浏览阅读1k次。centos8问题参考CentOS 8 EOL如何切换源? - 云服务器 ECS - 阿里云_"cenerrors during download metadata for repository \"appstream"

尚硅谷_谷粒学苑-微服务+全栈在线教育实战项目之旅_基于微服务的在线教育平台尚硅谷-程序员宅基地

文章浏览阅读2.7k次,点赞3次,收藏11次。SpringBoot+Maven+MabatisPlusmaven在新建springboot项目引入RELEASE版本出错maven在新建springboot项目引入RELEASE版本出错maven详解maven就是通过pom.xml中的配置,就能够从仓库获取到想要的jar包。仓库分为:本地仓库、第三方仓库(私服)、中央仓库springframework.boot:spring-boot-starter-parent:2.2.1.RELEASE’ not found若出现jar包下载不了只有两_基于微服务的在线教育平台尚硅谷

随便推点

网络学习第六天(路由器、VLAN)_路由和vlan-程序员宅基地

文章浏览阅读316次。路由的概念路由器它称之为网关设备。路由器就是用于连接不同网络的设备路由器是位于OSI模型的第三层。路由器通过路由决定数据的转发。网关的背景:当时每家计算机厂商,用于交换数据的通信程序(协议)和数据描述格式各不相同。因此,就把用于相互转换这些协议和格式的计算机称为网关。路由器与三层交换器的对比路由协议对比路由器的作用:1.路由寻址2.实现不同网络之间相连的功能3.通过路由决定数据的转发,转发策略称为 路由选择。VLAN相关技术什么是VLAN?中文名称叫:虚拟局域网。虚_路由和vlan

设置div背景颜色透明度,内部元素不透明_div设置透明度,里面的内容不透明-程序员宅基地

文章浏览阅读2.8w次,点赞6次,收藏22次。设置div背景颜色透明度,内部元素不透明:.demo{  background-color:rgba(255,255,255,0.15) } 错误方式:.demo{ background-color:#5CACEE;opacity:0.75;} 这样会导致div里面的元素内容和背景颜色一起变透明只针对谷歌浏览器的测试_div设置透明度,里面的内容不透明

Discuz!代码大全-程序员宅基地

文章浏览阅读563次。1.[ u]文字:在文字的位置可以任意加入您需要的字符,显示为下划线效果。2.[ align=center]文字:在文字的位置可以任意加入您需要的字符,center位置center表示居中,left表示居左,right表示居右。5.[ color=red]文字:输入您的颜色代码,在标签的中间插入文字可以实现文字颜色改变。6.[ SIZE=数字]文字:输入您的字体大小,在标签的中间插入文..._discuzcode 大全

iOS NSTimer定时器-程序员宅基地

文章浏览阅读2.6k次。iOS中定时器有三种,分别是NSTimer、CADisplayLink、dispatch_source,下面就分别对这三种计时器进行说明。一、NSTimerNSTimer这种定时器用的比较多,但是特别需要注意释放问题,如果处理不好很容易引起循环引用问题,造成内存泄漏。1.1 NSTimer的创建NSTimer有两种创建方法。方法一:这种方法虽然创建了NSTimer,但是定时器却没有起作用。这种方式创建的NSTimer,需要加入到NSRunLoop中,有NSRunLoop的驱动才会让定时器跑起来。_ios nstimer

Linux常用命令_ls-lmore-程序员宅基地

文章浏览阅读4.8k次,点赞17次,收藏51次。Linux的命令有几百个,对程序员来说,常用的并不多,考虑各位是初学者,先学习本章节前15个命令就可以了,其它的命令以后用到的时候再学习。1、开机 物理机服务器,按下电源开关,就像windows开机一样。 在VMware中点击“开启此虚拟机”。2、登录 启动完成后,输入用户名和密码,一般情况下,不要用root用户..._ls-lmore

MySQL基础命令_mysql -u user-程序员宅基地

文章浏览阅读4.1k次。1.登录MYSQL系统命令打开DOS命令框shengfen,以管理员的身份运行命令1:mysql -u usernae -p password命令2:mysql -u username -p password -h 需要连接的mysql主机名(localhost本地主机名)或是mysql的ip地址(默认为:127.0.0.1)-P 端口号(默认:3306端口)使用其中任意一个就OK,输入命令后DOS命令框得到mysql>就说明已经进入了mysql系统2. 查看mysql当中的._mysql -u user

推荐文章

热门文章

相关标签