問題を区間の数え上げとみなして考えましょう。以下では \((1, 2, \dots, M)\) の部分列であって \(l\) で始まって \(r\) で終わるものを 「区間 \([l, r]\) 」という風に考えます。

問題文の条件を満たす区間 \([l, r]\) は次のようなものです。

• \(1 \leq l \leq r \leq M\)
• \(A_i, B_i\) の少なくとも一方が \(l\) 以上 \(r\) 以下

これはナイーブなアルゴリズムで \(\mathrm{O}(M^2 N)\) 程度の計算量で数え上げることができますが、ここからさらに高速化していきましょう。
条件を満たす区間に関して、次の性質が成り立っています。

\(1 \leq i,j,k,l \leq M\) とする。
区間 \([k,l]\) が区間 \([i,j]\) を含んでいる、すなわち \(i,j,k,l\) が \(k \leq i \leq j \leq l\) の関係にあるとき、区間 \([i,j]\) が条件を満たすならば \([k,l]\) が条件を満たす。

• 直感的に言い換えると、「 \([i, j]\) が条件を満たしていれば、\(i\) を小さくしたり \(j\) を大きくしたりしても変わらず条件を満たしている」という感じです。

このような性質が成り立っているときは 尺取り法 と呼ばれるアルゴリズムを適用することができます。
尺取り法とは、次のような手続きで調べる区間を決めるアルゴリズムです。

• はじめ、\(L=R=1\) とする。
• \(L\) が \(M\) 以下の間、以下の操作を行う。
  • (1) 区間 \([L,R]\) が条件を満たさない間、\(R\) に \(1\) を足す。
  • (2) 条件を満たす \([L,R]\) が発見されたとする。このとき、区間 \([L,x]\) \((R\leq x \leq B)\) はすべて条件を満たすことになるので、その分を答えに加算する。
  • (3) \(L\) に \(1\) を加える。その後、\(L\) が \(M\) 以下ならば (1) に戻る。

このアルゴリズムのポイントは、区間の伸縮が全体で \(\mathrm{O}(M)\) 回に抑えられている点です。区間の長さが切り替わるのは \(L\) または \(R\) の値が \(1\) 増加したタイミングなので高々 \(2M\) 回に抑えられます。

よって、区間が条件を満たすかどうかの判定をしながら区間の伸び縮みを高速に行うことができれば、この問題全体を高速に解くことができます。これは、\(1 \leq i \leq N\) について「\([L, R]\) に \(A_i, B_i\) が何個入っているか？」を管理すればよいです。(詳しくは実装を参考にしてください。)
計算量は \(\mathrm{O}(N+M)\) になります。実装は次の通りです。

#include <iostream>
#include <vector>
using namespace std;

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> A(N), B(N);
  for (int i = 0; i < N; i++) cin >> A[i] >> B[i];
  vector<vector<int>> inv(M + 1);
  for (int i = 0; i < N; i++) {
    inv[A[i]].push_back(i);
    inv[B[i]].push_back(i);
  }
  vector<int> cnt(N), ans(M + 3);
  int cnt_zero = N;
  for (int i = 1, j = 1; i <= M;) {
    while (j <= M and cnt_zero != 0) {
      for (auto& x : inv[j]) {
        if (cnt[x] == 0) cnt_zero--;
        cnt[x]++;
      }
      j++;
    }
    if (cnt_zero != 0) break;
    ans[j - i]++, ans[M + 1 - i + 1]--;
    for (auto& x : inv[i]) {
      cnt[x]--;
      if (cnt[x] == 0) cnt_zero++;
    }
    i++;
  }
  for (int i = 1; i <= M; i++) {
    ans[i] += ans[i - 1];
    cout << ans[i] << " \n"[i == M];
  }
}