AcWing 4195. 线段覆盖(离散化+差分)
题目描述
在一个坐标轴上有 \(n\) 条线段。
每条线段的每个端点的坐标都为整数。
可能存在退化成点的线段。
线段之间可以相互交叉、嵌套甚至重合。
请你计算,对于每个 \(k \in\{1,2, \ldots, n\}\) ,坐标轴*有多少个整数坐标的点满足恰好被 \(k\) 条线段覆盖。
注意,左右端点分别为 \(l_{i}, r_{i}\) 的线段覆盖点 \(x\) 当且仅当 \(l_{i} \leq x \leq r_{i}\) 。
输入格式
第一行包含整数 \(n\)。
接下来 \(n\) 行,每行包含两个整数 \(l\_i,r\_i\),表示一条线段的左右端点。
输出格式
一行 \(n\) 个整数,其中第 \(i\) 个整数表示坐标轴中满足恰好被 \(i\) 条线段覆盖的整数坐标的点的数量。
数据范围
前三个测试点满足 \(1 \leq n \leq 3\) 。
所有测试点满足 \(1 \leq n \leq 2 \times 10^{5}, 0 \leq l_{i} \leq r_{i} \leq 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
算法
差分数组,对于第一个样例:
朴素做法如上,对于所有的点差分求前缀和即可,但是发现只要保存左右端点消息即可,端点和端点之间的点被线段覆盖的条数一定是一样的。
map做法:
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
typedef long long LL;
const int N = 200010;
map<LL, int> b;
LL ans[N];
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
{
LL l, r;
scanf("%lld%lld", &l, &r);
b[l] ++, b[r + 1] -- ;
}
LL sum = 0, last = -1;
for (auto& [k, v]: b)
{
if (last != -1) ans[sum] += k - last;
sum += v;
last = k;
}
for (int i = 1; i <= n; i ++ )
printf("%lld ", ans[i]);
return 0;
}
离散化后差分:
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1000010;
LL l[N], r[N], res[N], x[N];
vector<LL> all;
int n, m;
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i++)
{
scanf("%lld%lld", &l[i], &r[i]);
r[i]++;
all.push_back(l[i]);
all.push_back(r[i]);
}
sort(all.begin(), all.end());
all.erase(unique(all.begin(), all.end()), all.end());
m = all.size();
for(int i = 0 ; i < n; i++)
{
int pos1 = lower_bound(all.begin(), all.end(), l[i]) - all.begin();
int pos2 = lower_bound(all.begin(), all.end(), r[i]) - all.begin();
x[pos1]++;
x[pos2]--;
}
LL sum = 0;
for(int i = 0; i < m; i++){
if(i != 0){
res[sum] += all[i] - all[i - 1];
}
sum += x[i];
}
for(int i = 1; i <= n; i++)
cout<<res[i]<<" ";
return 0;
}