SOJ1711 题解
题意
给定 \(n\) 个在数轴的区间 \([l_1,r_1],[l_2,r_2],...,[l_n,r_n]\)。
定义 \(I(x)\) 为所有包含 \([x,x+1]\) 的区间形成的集合,即 \(I(x)=\{k \mid [x,x+1] \subseteq [l_k,r_k] \}\)。
称一个数列 \(S\) 是好的当且仅当存在一个整数 \(x\) 满足 \(I(x)\) 中的元素从小到大排序后等于 \(S\) 且 \(S\) 的长度非 \(0\)。
给定 \(k\),求字典序第 \(k\) 小的好的数列。如果好数列的数量不足 \(k\) 个,输出 -1
。
\(1 \le n \le 3 \times 10^5,1 \le k \le 10^{18},0 \le l_i < r_i \le 10^9\)。
题解
考试的题目。然而我并不会……
很羡慕 positive1 大师,1h 就切掉了,而我想了 2h 仍然毫无头绪……是套路见少了,还是思维质量不行,或是二者兼有?
显然可以先离散化,那么就是 \(2n\) 个小区间。则 \(k\) 一定小于 \(2n\)。
求字典序第 \(k\) 小,则枚举每一位放什么。也就是要求包含 \(i\) 的不同 \(I(x)\) 的数量。
那么先对 \(I(x)\) 离散化。这个可以用哈希解决。
设当前枚举到第 \(i\) 个区间,则要求 \(l_i\) 到 \(r_i\) 间不同颜色的数量。同时,\(i\) 之前的区间对 \(i\) 有影响:必须包含之前选的区间,不包含之前不选的区间。
此时我们发现问题转化为了区间数颜色与区间覆盖。看数据范围,不能用线段树与 \(\text{bitset}\),然后就不会做了……(有人用 \(\text{ODT}\) 做,应该能卡?不过我也不会)
实际上,有一个很好的性质:对于任意两个颜色相等的位置 \(x,y\),一定有 \(\forall i,([l_i,r_i] \subseteq [x,y]) \vee ([x,y] \subseteq [l_i,r_i]) \vee ([l_i,r_i] \cap [x,y]=\varnothing)=1\)(可能没有考虑边界情况)。读者自证不难。
那么一个区间若包含某种颜色 \(i\),则必然包含所有颜色为 \(i\) 的位置。于是只在第一个位置算颜色 \(i\) 的贡献。那么就容易用线段树维护了。
最新文章
- asp.net 上一条和下一条记录的显示
- launch文件
- JSP内置标签 JSP中JavaBean标签 JSP开发模式 EL和JSTL快速入门
- vi模式
- javaweb项目的优化 - 几番思念
- Date对象
- Oracle改变字段类型
- PHP操作mysql类
- 解决adb push时出现的";Read-only file system";问题
- XML (一)
- centos安装软件依赖问题
- 数据挖掘_requests模块的post方法
- 关于spring aop Advisor排序问题
- krpano生成全景图
- 网页中嵌入google地图
- SQL求几何重心
- Spring framewrok 源码概览
- vsts 管理 持续集成 跟自动化测试
- ReactiveX 学习笔记(11)对 LINQ 的扩展
- 【DS】排序算法之选择排序(Selection Sort)