hihoCoder - 1079 - 离散化 (线段树 + 离散化)

#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<b_i<=L。

输出

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

例子输入
5 10
4 10
0 2
1 6
5 9
3 4
例子输出
5



待理解。。。


AC代码:

#include <map>
#include <set>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <cstdio>
#include <cctype>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define INF 0x7fffffff
using namespace std;const int maxn = 200005;struct Poster {int l, r;
}pt[maxn];struct Tree {int l ,r;int c;int mid() { return (l + r) >> 1; }
}node[maxn << 2];int d[maxn];
int c;int used[maxn];void build(int l, int r, int rt) {node[rt].l = l;node[rt].r = r;node[rt].c = 0;if(l + 1 == r) {return;}int mid = node[rt].mid();build(l, mid, rt << 1);build(mid, r, rt << 1 | 1);
}void update(int l, int r, int c, int rt) {if(l <= node[rt].l && node[rt].r <= r) {node[rt].c = c;return;}int mid = node[rt].mid();if(node[rt].c != -1) {	//有新的海报贴进来,所以说要将当前这一块往下更新 node[rt << 1].c = node[rt << 1 | 1].c = node[rt].c;node[rt].c = -1;}//对于当前区间的三种情况 if (r <= mid) update(l, r, c, rt << 1);else if (l >= mid) update(l, r, c, rt << 1 | 1);else{update(l, mid, c, rt << 1);update(mid, r, c, rt << 1 | 1);}
}void query(int rt)
{if (node[rt].c != -1){used[node[rt].c] = 1;return;}query(rt << 1);query(rt << 1 | 1);
}int main() {int n, l;scanf("%d %d", &n, &l);if(n == 0) {printf("0\n");return 0;}c = 0;for(int i = 1; i <= n; i ++) {scanf("%d %d", &pt[i].l, &pt[i].r);d[c ++] = pt[i].l;d[c ++] = pt[i].r;used[i] = 0;}sort(d, d + c);c = unique(d, d + c) - d; //去重 //	for(int i = 0; i < c; i ++) {
//		cout << d[i] << " ";
//	}
//	cout << endl;build(0, 2 * c + 1, 1);for(int i = 1; i <= n; i ++) { //模拟离散化贴海报的过程。从1到n张海报 int x = lower_bound(d, d + c, pt[i].l) - d;int y = lower_bound(d, d + c, pt[i].r) - d;
//		cout << x << " " << y << " " << (x << 1) << " " << (y << 1 | 1)  << endl;update(x << 1, y << 1 | 1, i, 1);}query(1);int ans = 0;for (int i = 1; i <= n; i ++) ans += used[i];printf("%d\n", ans);return 0;
}










转载于:https://www.cnblogs.com/jhcelue/p/6908782.html

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:https://dhexx.cn/news/show-18534.html

如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网进行投诉反馈,一经查实,立即删除!


相关文章:

  • poj 2442 Sequence
  • bzoj 3676: [Apio2014]回文串
  • Linux ssh服务开启秘钥和密码认证
  • Spring Boot和Dubbo整合
  • ufldl学习笔记与编程作业:Linear Regression(线性回归)
  • Python-面向对象之一
  • 浅析我对代码规范的理解
  • Swift - 实现tableView单选系统样式
  • Problems with Ribbon/Feign/Zuul retry
  • 绝大多数人努力程度之低,根本轮不上拼天赋
  • GDTR与LDTR
  • c#之正则表达式
  • Makefile文件(一)_介绍
  • 高级控件 下(三)
  • ArcGIS Python实现Modis NDVI批量化月最大合成
  • crmjs区分窗口是否是高速编辑(2)
  • jQuery Validate验证框架(转载)
  • MD5生成
  • Python_代码练习_写一个判断是否为小数的函数
  • 异常处理-try catch
  • ES6中Number中的扩展
  • 20169302 2016-2017-2 《网络攻防实践》课程总结
  • 九度OJ1451题-信封错装
  • PHP compact
  • Selenium 方法封装 一
  • 访问win10的远程桌面(Remote Desktop)总是凭据或者用户密码错误
  • angular2 --使用DecimalPipe格式化数字
  • 【bzoj1520】[POI2006]Szk-Schools 费用流
  • JQ 按钮实现两种功能
  • 存储控制器和SDRAM 实验
  • Phalcon调试大杀器之phalcon-debugbar安装
  • python sys与shutil模块
  • netty学习指南
  • 关于人生观与方法论的两篇文章
  • Java 8 新特性:3-函数(Function)接口
  • 通过js控制层的动态隐藏
  • iOS自动布局高级用法 纯代码约束写法
  • vue组件(Vue+webpack项目实战系列之三)
  • 6.20
  • 产业企业和投资机会研究 沈阳新松机器人自动化股份有限公司(300024)
  • idea整个项目乱码解决办法
  • 从头认识java-16.4 nio的读与写(ByteBuffer的使用)
  • 宿命的PSS
  • 07_上午内容回顾
  • python三维可视化:配置tvtk
  • working copy is not up-to-date
  • 1.strcpy使用注意
  • html中设置锚点定位的几种常见方法
  • elasticsearch.net search入门使用指南中文版(翻译)
  • 重写( override)and 重载(overload)