この問題はいわゆる imos法と呼ばれるテクニックの練習問題です。

制約上 \(L_i>R_i\) なこともありますが、交換して \(L_i<R_i\) としても答えは変わりません。以降 \(L_i<R_i\) を仮定します。

愚直な解法として各バス停を通る路線の本数のカウンタ \(C\) を用意して、各路線について停まるバス停を列挙してそれぞれのバス停のカウンタを \(1\) 増やすという解法が考えられます。しかし、各路線は最大で \(N\) 個のバス停に停車するため時間計算量 \(\Theta (NM)\) となり、今回の制約では実行時間制限を超過してしまいます。

では愚直に列挙せずにカウンタをうまく管理する方法を考えましょう。各バス路線は \(L_i\) 以上 \(R_i\) 以下のバス停のカウンタに \(1\) 加算します。このとき、 \(C_{L_i}-C_{L_i-1}\) が1増加し、 \(C_{R_i+1}-C_{R_i}\) が \(1\) 減少します。愚直な解法の \(C\) に対する操作は \(C\) の差分の列に対して \(2\) 要素だけ操作することに対応します。つまり、各路線の更新は \(C\) の差分の列に対しては定数個の変更だけで可能です。\(C\) の差分の列を管理し、すべての路線について操作が終わってから \(C\) を復元すれば高速に \(C\) が求まることがわかります。このテクニックがimos法と呼ばれるものです。

時間計算量は \(\mathrm{O}(N+M)\) になります。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> imos(n + 1);
    for (int i = 0; i < m; i++) {
        int l, r;
        cin >> l >> r;
        if (l > r)
            swap(l, r);
        l--;
        imos[l]++;
        imos[r]--;
    }
    for (int i = 0; i < n; i++) {
        imos[i + 1] += imos[i];
    }
    for (int i = 0; i < n; i++) {
        cout << imos[i] << " \n"[i == n - 1];
    }
}