C. Covered Points Count

题意

给N条线段，这些线段可以覆盖至少一个点，求被1～N条线段覆盖的点各有多少个？
input

3
0 3
1 3
3 8

output

6 2 1

样例解释

样例解释

分析

开始为一条高度为0直线，对于每一条线段[l,r]，我们就让位于[l,r]部分高度-1，处理完之后，某个点下降了多少高度就是被多少条线段所覆盖。
从这里就已经可以看出来是一个典型的差分题，让位于[l,r]部分高度-1，就是差分数组B[l]-=1,B[r+1]+=1, 处理完之后再还原成原始高度数组即可。但是此题还涉及了离散化，所以不能一个点一个点的算，而需要按线段来算(其实就是离散化还原)

代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn = 1e6+10;

int N;
ll pos[maxn][2];
ll cnt[maxn],B[maxn];
vector<ll> ve;

int ind(ll x){ //离散定位
    int idx = lower_bound(ve.begin(),ve.end(),x)-ve.begin();
    return idx;
}

int main(){
    cin>>N;
    ll a,b;
    for(int i = 0;i<N;i++){
        scanf("%lld %lld",&a,&b);
        if(a>b) swap(a,b);
        pos[i][0] = a,pos[i][1] = b+1;
        ve.push_back(a);
        ve.push_back(b+1);
    }
    sort(ve.begin(),ve.end());
    ve.erase(unique(ve.begin(),ve.end()),ve.end());
    for(int i = 0;i<N;i++){
        a = pos[i][0],b = pos[i][1];
        int id1 = ind(a),id2 = ind(b);
        B[id1]-=1;
        B[id2]+=1;
    }
    for(int i = 0;i<ve.size()-1;i++){
        if(i) B[i] = B[i-1]+B[i];
        cnt[abs(B[i])] += ve[i+1]-ve[i];//B[i]下降高度
    }
    for(int i = 1;i<=N;i++) printf("%lld ",cnt[i]);
    return 0;
}