CF-1000C Covered Points Count 题解

题目大意

在一个数轴上，给你n个线段，每个线段可以相交，重合，问你被覆盖$1$~$n$次的点每个有多少。

解题思路

上次上课讲到了离散化差分，去搜了搜，就找到了这个题目。。

因为线段的端点数值很大，$1·10^{18}$，但是n的数据范围不大。

所以可以使用离散化，

那么差分之后的数组代表着一段的覆盖次数，这一段的长度为相邻两点的差。

线段可以重合，需要去重。

完整代码

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N = 2e5 + 500;
struct {
	ll x, y;
}p[N];
ll pos[N << 1], num[N << 1], cnt[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,c = 0;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> p[i].x >> p[i].y;
		pos[++c] = p[i].x,pos[++c] = p[i].y + 1;
	}
	sort(pos + 1, pos + 1 + c);
	int l = unique(pos + 1, pos + 1 + c) - pos - 1;//去重
	for (int i = 1; i <= n; i++) {
		int x = lower_bound(pos + 1, pos + 1 + l, p[i].x) - pos;//注意，lower_bound的返回值为与传入的数组起始地址的相对位置，所以num是从1开始的。
		int y = lower_bound(pos + 1, pos + 1 + l, p[i].y + 1) - pos;//查找y+1
		num[x]++, num[y]--;
	}
	for (int i = 1; i < l; i++) {
		num[i] += num[i - 1];//这一段的覆盖数量
		cnt[num[i]] += pos[i+1]-pos[i];//这一段的长度
	}
	for (int i = 1; i <= n; i++)	printf("%lld%c", cnt[i], i == n ? '\n' : ' ');
}