B07.js

// この問題は、\*\*差分配列（いもす法）\*\*を使うことで高速に解けます。
// 各従業員が出勤する時に +1、退勤する時に -1 をして、累積和をとることで、
// **時刻 t+0.5 に店内にいる人数**を O(N+T) で計算できます。

// ---

// ### 🔧 アプローチ（いもす法）

// * `cnt[i]` を「時刻 `i + 0.5` に店内にいる人数」とすると、

//   * 従業員 `(L, R)` がいたとき：

//     * `cnt[L] += 1`
//     * `cnt[R] -= 1`
// * 最後に累積和を取って `cnt[0]` ～ `cnt[T-1]` を出力。

// ### ✅ JavaScript (Node.js, `fs`使用)

const fs = require('fs');

const input = fs.readFileSync('/dev/stdin', 'utf8').trim().split('\n');
const T = parseInt(input[0], 10);
const N = parseInt(input[1], 10);

// 差分配列の初期化
const cnt = new Array(T + 1).fill(0);

// 各従業員の出退勤を処理
for (let i = 0; i < N; i++) {
    const [L, R] = input[2 + i].split(' ').map(Number);
    cnt[L] += 1;
    cnt[R] -= 1;
}

// 累積和をとって出力
let current = 0;
for (let t = 0; t < T; t++) {
    current += cnt[t];
    console.log(current);
}

// ### 📈 実行時間とメモリ

// * 実行時間：O(N + T)
// * メモリ使用量：配列 `cnt` のサイズは最大 500,001 要素 → 約 4MB 以下

// ---

// ### 🧠 図による解説（例）

// 入力：

// ```
// T = 10, N = 3
// [L, R] = [0,3], [2,4], [1,3]
// ```

// 差分配列に追加：

// | 時刻 `t` | cnt\[t]（差分） |
// | ------ | ----------- |
// | 0      | +1          |
// | 1      | +1          |
// | 2      | +1          |
// | 3      | -3          |
// | 4      | -1          |

// 累積和を取ると：

// | t   | cnt (合計人数) |
// | --- | ---------- |
// | 0.5 | 1          |
// | 1.5 | 2          |
// | 2.5 | 3          |
// | 3.5 | 0          |
// | 4.5 | 0          |
// | ... | ...        |

// ---

// ### ✅ 注意

// * 差分配列の添字は `[0, T]` まで必要（R == T の人に対応）
// * 出力は `console.log` を T 回実行して OK（T = 5e5 まで問題なし）