acwing4195. 线段覆盖（差分）

在一个坐标轴上有 nn 条线段。
每条线段的每个端点的坐标都为整数。
可能存在退化成点的线段。
线段之间可以相互交叉、嵌套甚至重合。
请你计算，对于每个 k∈{1,2,…,n}k∈{1,2,…,n}，坐标轴中共有多少个整数坐标的点满足恰好被 kk 条线段覆盖。
注意，左右端点分别为 li,rili,ri 的线段覆盖点 xx 当且仅当 li≤x≤rili≤x≤ri。

输入格式

第一行包含整数 nn。
接下来 nn 行，每行包含两个整数 li,rili,ri，表示一条线段的左右端点。

输出格式

一行 nn 个整数，其中第 ii 个整数表示坐标轴中满足恰好被 ii 条线段覆盖的整数坐标的点的数量。

数据范围

前三个测试点满足 1≤n≤31≤n≤3。
所有测试点满足 1≤n≤2×1051≤n≤2×105，0≤li≤ri≤10180≤li≤ri≤1018。

输入样例1：

3 0 3 1 3 3 8

输出样例1：

6 2 1

输入样例2：

3 1 3 2 4 5 7

输出样例2：

5 2 0

#include<iostream>
#include<map>;
using namespace std;
typedef long long LL;
const int N = 200010;
map<LL,int>b;
LL res[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) res[sum] += k - last;
        last = k;
        sum += v;
    }
    for(int i = 1; i <= n; ++i){
        printf("%lld ",res[i]);
    }
    return 0;
}