思路:
扫描线:
按照端点分分区间最多可以分2n个区间,每个区间内部单独统计.每个区间内的所有点被覆盖的次数都相同
取左端点的位置和右端点的下一个位置,将所有位置放在一起排序,从左到右遍历每个区间的端点,将区间的权值连续累加起来,表示当前区间内每个点被覆盖的次数
差分+map:
用map来代替差分数组,来一个区间将区间内其所有点加一,表明区间内每个点被覆盖的次数又多了一个,b[l]+=1,b[r+1]-=1;
map自动对所有端点排序,n个区间共有2n个端点,last表示上一个区间的端点,初始值设置为-1,用于计算区间长度.
for(auto &[k,v]:b)从小到大枚举每个端点,k为端点,v为端点对应的差分值;
map将区间离散化成端点后,由sum计算当前端点前缀和,枚举过程中sum+=v,sum就是当前区间所有点被覆盖的次数,
res[N],为统计被覆盖次数为i的点的数量,对于当前区间所有点都被被覆盖sum次,区间长度k-last就是被覆盖sum次点的数量,res[sum]+=k-last;
统计完当前区间的情况后更新 sum+=v,last=k,继续统计下一个区间
注意:对第一个区间进行了特判,整个循环先计算前缀和再进行统计
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5+10;
map<LL,int>b;
LL res[N];//res为被覆盖i次的点数量
int main()
{
int n;
cin>>n;
for (int i = 0; i < n; i ++ )
{
LL l,r;
cin>>l>>r;
b[l]+=1;//离散化区间到map中,点与点之间对应的值都是相同的
b[r+1]-=1;
}
LL last=-1;
int sum=0;//sum为区间内每个点的被覆盖段数,计算前缀和得到
for(auto &[k,v]:b)//枚举map的每一个键值对,k为键值,v为权值
{
if(last!=-1)//当当前区间不是第一个区间时
{
res[sum]+=k-last;//统计被覆盖sum次的点数,加上当前区间的长度
}
sum+=v;//计算每段的前缀和,也就是该段内点被多少区间覆盖
last=k;//将last更新为当前端点k
}
for(int i=1;i<=n;i++)
cout<<res[i]<<" ";
}