官方题解

题目大意

给出 $n$ 名用户的起始登录时间以及连续登录天数，问对于每一个满足 $1\leq k\leq n$ 的整数 $k$ ，恰好有 $k$ 人登录的天数。

解题思路

对于每一名用户，其对应登录的时间为一段连续的区间，不难想到使用差分前缀和来维护每天登录的人数。但由于数据范围较大，无法直接使用数组进行维护，考虑离散化，仅记录差分记录的时间点，因为前缀和后，相邻差分数组元素之间的值都是相等的，所以我们得到这段区间的值 $val$ 后可以直接计算出这段区间的长度 $len$ ，即为恰好有 $val$ 人的天数需要增加 $len$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 200010;

int l[N],r[N];
int d[2*N];
int cnt[N];

int main(){
    int n;cin>>n;
    vector<int>a;
    for(int i=1;i<=n;i++){
        cin>>l[i]>>r[i];
        a.push_back(l[i]);
        a.push_back(l[i]+r[i]);
    }
    sort(a.begin(),a.end());
    a.erase(unique(a.begin(),a.end()),a.end());

    map<int,int>mp,id;
    int idx=0;
    for(auto x:a){
        mp[x]=++idx;
        id[idx]=x;
    }

    for(int i=1;i<=n;i++){
        d[mp[l[i]]]++;
        d[mp[l[i]+r[i]]]--;
    }
    for(int i=1;i<=idx;i++) d[i]+=d[i-1];

    for(int i=1;i<idx;i++){
        int L=id[i],R=id[i+1]-1;
        cnt[d[i]]+=R-L+1;
    }
    for(int i=1;i<=n;i++) cout<<cnt[i]<<" ";
    return 0;
}