热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

hihocoder#1079:离散化线段树应用

#1079:离散化时间限制:10000ms单点时限:1000ms内存限制:256MB描述小Hi和小Ho在回国之后,重新过起了朝7晚5的学生生活,当然了,他们还是在一直学习着各种算法

#1079 : 离散化

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Hi和小Ho在回国之后,重新过起了朝7晚5的学生生活,当然了,他们还是在一直学习着各种算法~

这天小Hi和小Ho所在的学校举办社团文化节,各大社团都在宣传栏上贴起了海报,但是贴来贴去,有些海报就会被其他社团的海报所遮挡住。看到这个场景,小Hi便产生了这样的一个疑问——最后到底能有几张海报还能被看见呢?

于是小Ho肩负起了解决这个问题的责任:因为宣传栏和海报的高度都是一样的,所以宣传栏可以被视作长度为L的一段区间,且有N张海报按照顺序依次贴在了宣传栏上,其中第i张海报贴住的范围可以用一段区间[a_i, b_i]表示,其中a_i, b_i均为属于[0, L]的整数,而一张海报能被看到当且仅当存在长度大于0的一部分没有被后来贴的海报所遮挡住。那么问题就来了:究竟有几张海报能被看到呢?

提示一:正确的认识信息量

提示二:小Hi大讲堂之线段树的节点意义

输入

每个测试点(输入文件)有且仅有一组测试数据。

每组测试数据的第1行为两个整数N和L,分别表示总共贴上的海报数量和宣传栏的宽度。

每组测试数据的第2-N+1行,按照贴上去的先后顺序,每行描述一张海报,其中第i+1行为两个整数a_i, b_i,表示第i张海报所贴的区间为[a_i, b_i]。

对于100%的数据,满足N<=10^5,L<=10^9,0<=a_i

输出

对于每组测试数据,输出一个整数Ans,表示总共有多少张海报能被看到。

样例输入
5 10
4 10
0 2
1 6
5 9
3 4
样例输出
5
注意点
连续型线段树一段区间是分解成为[l, m], [m + 1, r]
#include 
#include
#include
#include
#include<set>
#include
using namespace std;
const int max_N = 100000;
int a[max_N+1], b[max_N+1];
int value[max_N<<2] = {0};
int N, L, left_bound = 1, right_bound = 0;
void read_and_compress(){
    set<int> s;
    map<int, int> m;
    scanf("%d %d", &N, &L);
    for(int i = 1; i <= N; ++i){
        scanf("%d %d", &a[i], &b[i]);
        s.insert(a[i]);
        s.insert(b[i]);
    }
    right_bound = 0;
    for(set<int>::iterator it = s.begin(); it != s.end(); ++it){
        m[*it] = ++right_bound;
    }
    for(int i = 1; i <= N; ++i){
        a[i] = m[a[i]];
        b[i] = m[b[i]];
    }
}
void push_down(int value[], int idx){
    if(value[idx] > 0){
        value[idx<<1] = value[idx];
        value[(idx<<1)|1] = value[idx];
        value[idx] = 0;
    }
}
void update(int value[], int idx, int left, int right, int l, int r, int v){
    if(l >= r || r <= left || l >= right || left >= right) return;
    if(l <= left && right <= r){
        value[idx] = v;
    }else{
        push_down(value, idx);
        int mid = (left + right) >> 1;
        if(l 1, left, mid, l, r, v);
        if(mid 1)|1, mid, right, l, r, v);
    }
}
void query(int value[], int idx, int left, int right, int l, int r, set<int> &s){
    if(l >= r || left >= right || r <= left || l >= right) return;
    if(value[idx] > 0){
        s.insert(value[idx]);
    }else if(left + 1 < right){
        int mid = (left + right) >> 1;
        query(value, idx<<1, left, mid, l, r, s);
        query(value, (idx<<1)|1, mid, right, l, r, s);
    }
}
void print_tree(int[], int, int, int);
int main(){
    read_and_compress();
    for(int i = 1; i <= N; ++i){
        update(value, 1, left_bound, right_bound, a[i], b[i], i);
    }
    set<int> s;
    query(value, 1, left_bound, right_bound, left_bound, right_bound, s);
    int ans = s.size();
    printf("%d\n", ans);
    return 0;
}

hihocoder #1079 : 离散化-线段树应用


推荐阅读
  • 本文内容为asp.net微信公众平台开发的目录汇总,包括数据库设计、多层架构框架搭建和入口实现、微信消息封装及反射赋值、关注事件、用户记录、回复文本消息、图文消息、服务搭建(接入)、自定义菜单等。同时提供了示例代码和相关的后台管理功能。内容涵盖了多个方面,适合综合运用。 ... [详细]
  • 基于layUI的图片上传前预览功能的2种实现方式
    本文介绍了基于layUI的图片上传前预览功能的两种实现方式:一种是使用blob+FileReader,另一种是使用layUI自带的参数。通过选择文件后点击文件名,在页面中间弹窗内预览图片。其中,layUI自带的参数实现了图片预览功能。该功能依赖于layUI的上传模块,并使用了blob和FileReader来读取本地文件并获取图像的base64编码。点击文件名时会执行See()函数。摘要长度为169字。 ... [详细]
  • Mac OS 升级到11.2.2 Eclipse打不开了,报错Failed to create the Java Virtual Machine
    本文介绍了在Mac OS升级到11.2.2版本后,使用Eclipse打开时出现报错Failed to create the Java Virtual Machine的问题,并提供了解决方法。 ... [详细]
  • 在说Hibernate映射前,我们先来了解下对象关系映射ORM。ORM的实现思想就是将关系数据库中表的数据映射成对象,以对象的形式展现。这样开发人员就可以把对数据库的操作转化为对 ... [详细]
  • 本文介绍了在SpringBoot中集成thymeleaf前端模版的配置步骤,包括在application.properties配置文件中添加thymeleaf的配置信息,引入thymeleaf的jar包,以及创建PageController并添加index方法。 ... [详细]
  • 本文详细介绍了Linux中进程控制块PCBtask_struct结构体的结构和作用,包括进程状态、进程号、待处理信号、进程地址空间、调度标志、锁深度、基本时间片、调度策略以及内存管理信息等方面的内容。阅读本文可以更加深入地了解Linux进程管理的原理和机制。 ... [详细]
  • 1,关于死锁的理解死锁,我们可以简单的理解为是两个线程同时使用同一资源,两个线程又得不到相应的资源而造成永无相互等待的情况。 2,模拟死锁背景介绍:我们创建一个朋友 ... [详细]
  • 后台获取视图对应的字符串
    1.帮助类后台获取视图对应的字符串publicclassViewHelper{将View输出为字符串(注:不会执行对应的ac ... [详细]
  • 《数据结构》学习笔记3——串匹配算法性能评估
    本文主要讨论串匹配算法的性能评估,包括模式匹配、字符种类数量、算法复杂度等内容。通过借助C++中的头文件和库,可以实现对串的匹配操作。其中蛮力算法的复杂度为O(m*n),通过随机取出长度为m的子串作为模式P,在文本T中进行匹配,统计平均复杂度。对于成功和失败的匹配分别进行测试,分析其平均复杂度。详情请参考相关学习资源。 ... [详细]
  • 本文介绍了通过ABAP开发往外网发邮件的需求,并提供了配置和代码整理的资料。其中包括了配置SAP邮件服务器的步骤和ABAP写发送邮件代码的过程。通过RZ10配置参数和icm/server_port_1的设定,可以实现向Sap User和外部邮件发送邮件的功能。希望对需要的开发人员有帮助。摘要长度:184字。 ... [详细]
  • 本文介绍了lua语言中闭包的特性及其在模式匹配、日期处理、编译和模块化等方面的应用。lua中的闭包是严格遵循词法定界的第一类值,函数可以作为变量自由传递,也可以作为参数传递给其他函数。这些特性使得lua语言具有极大的灵活性,为程序开发带来了便利。 ... [详细]
  • 本文介绍了使用Java实现大数乘法的分治算法,包括输入数据的处理、普通大数乘法的结果和Karatsuba大数乘法的结果。通过改变long类型可以适应不同范围的大数乘法计算。 ... [详细]
  • HDU 2372 El Dorado(DP)的最长上升子序列长度求解方法
    本文介绍了解决HDU 2372 El Dorado问题的一种动态规划方法,通过循环k的方式求解最长上升子序列的长度。具体实现过程包括初始化dp数组、读取数列、计算最长上升子序列长度等步骤。 ... [详细]
  • Java验证码——kaptcha的使用配置及样式
    本文介绍了如何使用kaptcha库来实现Java验证码的配置和样式设置,包括pom.xml的依赖配置和web.xml中servlet的配置。 ... [详细]
  • 高质量SQL书写的30条建议
    本文提供了30条关于优化SQL的建议,包括避免使用select *,使用具体字段,以及使用limit 1等。这些建议是基于实际开发经验总结出来的,旨在帮助读者优化SQL查询。 ... [详细]
author-avatar
-DJIAJIAN-
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有