Scanline--An efficient way to count numbers of covers

Problem: Line Covers

There are n line segments on a coordinate axis.

The coordinates of each endpoint of each line segment are integers.

There may be line segments that degenerate into points.

Line segments can cross, nest or even overlap each other.

Calculate, for each k ∈ {1,2,...,n}, the total number of points in the axis with integer coordinates satisfying exactly the k line segments covered.

Note that the line segments with left and right endpoints li, ri cover point x if and only if li≤x≤ri.

Input format

The first line contains the integer n.

The next n lines, each containing two integers li, ri represent the left and right endpoints of a line segment.

Output format

A row of n integers, where the i-th integer represents the number of points in the axis that satisfy the integer coordinates exactly covered by i line segments.

Data range

The first three test points satisfy 1 ≤ n ≤ 3. All test points satisfy 1≤n≤2×10^5 and 0≤li≤ri≤10^18.

Analysis

The first thought in my mind is to declare an array of size $$10^{18}$$ to record the counts. However, $$10^{18} * 4$$ Bytes is an too large space for us.

Of course, we can use brute force, simply iterating for each line segment and count. However, the time complexity will reach O(mn)， in which m is the range of the value of end points.

So, to reduce both time complexity and space complexity, we could use scanline.

Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>

using namespace std;

static const int N = 200001;

typedef long long LL;

map<LL, int> m;
LL d[N];
int n;

int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        LL a, b;
        scanf("%lld%lld", &a, &b);
        m[a]++;
        m[b+1]--;
    }

    LL sum = 0, last = -1;
    for(auto &[k, v]:m){
        if(last != -1){
            d[sum] += k - last;
        }
        last = k;
        sum += v;
    }

    for(int i = 1; i <= n; i++){
        printf("%lld ", d[i]);
    }
}