4195 线段覆盖(差分)
1. 问题描述:
在一个坐标轴上有 n 条线段。每条线段的每个端点的坐标都为整数。可能存在退化成点的线段。线段之间可以相互交叉、嵌套甚至重合。请你计算,对于每个 k∈{1,2,…,n},坐标轴中共有多少个整数坐标的点满足恰好被 k 条线段覆盖。注意,左右端点分别为 li,ri 的线段覆盖点 x 当且仅当 li ≤ x ≤ ri。
输入格式
第一行包含整数 n。接下来 n 行,每行包含两个整数 li,ri,表示一条线段的左右端点。
输出格式
一行 n 个整数,其中第 i 个整数表示坐标轴中满足恰好被 i 条线段覆盖的整数坐标的点的数量。
数据范围
前三个测试点满足 1 ≤ n ≤ 3。
所有测试点满足 1 ≤ n ≤ 2 × 10 ^ 5,0 ≤ li ≤ ri ≤ 10 ^ 18。
输入样例1:
3
0 3
1 3
3 8
输出样例1:
6 2 1
输入样例2:
3
1 3
2 4
5 7
输出样例2:
5 2 0
来源:https://www.acwing.com/problem/content/description/4198/
2. 思路分析:
分析题目可以知道已知若干个线段,我们需要求解出被i条线段覆盖的点的数目(i = 1 ~n),相当于每一条线段都有一个权值1,我们需要将每条线段对应区间的所有数字加上一个1,由这个特点可以知道属于经典的差分模型,使用差分的模板即可,因为l和r的范围比较大所以需要离散化(一般差分的题目都会加上离散化来提高难度,一般大于10 ^ 6的都需要离散化因为声明不了那么大的数组),离散化一般有两种方式,第一种是使用哈希表进行离散化,第二种是自己手写离散化,手写离散化的方式代码比较麻烦但是运行效率比较高(对于c++代码来说效率比较高一点但是python好像手写离散化效率也不高,反而运行效率更低),为了方便编写代码这里我们可以采用哈希表进行离散化:
对区间[l,r]所有数字加上1在差分操作中相当于是mp[l] += 1,mp[r + 1] -= 1,因为需要包含第r个点所以是r + 1减去1,最终需要求解的是整数点被线段覆盖i次的数目,所以我们可以枚举一下从小到大排序之后的哈希表,相邻两段横坐标的差值就是当前出现s次的整数点的数量,s为当前离散化之后差分数组的前缀和,差分数组的前缀和就是原数组每一个点的权值。
3. 代码如下:
class Solution:
def process(self):
n = int(input())
mp = dict()
for i in range(n):
a, b = map(int, input().split())
if a not in mp:
mp[a] = 1
else:
mp[a] += 1
# 因为包括第b个点所以是下一个位置减1
if b + 1 not in mp:
mp[b + 1] = -1
else:
mp[b + 1] -= 1
# 对字典进行排序, 得到的是一个列表, 列表的元素为键值对的元组类型, 排序之后相当于是从数轴的左边枚举到右边
mp = sorted(mp.items(), key=lambda x: x[0])
res = dict()
# last记录上一个横坐标的位置
s, last = 0, -1
for i in range(len(mp)):
k, v = mp[i][0], mp[i][1]
# last = -1时表示没有上一段, 只有当last!= -1的时候表示有上一段
if last != -1:
if s not in res:
# 相邻两段横坐标的差值就是出现s次的整数点的数目
res[s] = k - last
else:
res[s] += k - last
s += v
last = k
for i in range(1, n + 1):
if i not in res:
print(0, end=" ")
else:
print(res[i], end=" ")
if __name__ == '__main__':
Solution().process()