Let us try counting the number of segments. Here we regard a contiguous subsequence of \((1, 2, \dots, M)\) starting with \(l\) and ending with \(r\) as a “segment \([l, r]\).”

A segment \([l, r]\) satisfies the conditions in the Problem Statement if:

• \(1 \leq l \leq r \leq M\), and
• at least one of \(A_i\) and \(B_i\) is between \(l\) and \(r\), inclusive.

The count can be found with a naive algorithm in a total of \(\mathrm{O}(M^2 N)\) time. Now let us optimize it.
The following property holds about the segments satisfying the conditions:

Let \(1 \leq i,j,k,l \leq M\).
If the segment \([k,l]\) contains the segment \([i,j]\), that is, if \(i,j,k\), and \(l\) satisfy \(k \leq i \leq j \leq l\), then if the segment \([i,j]\) satisfies the conditions, so does the segment \([k,l]\).

• Intuitively, we can say: “if \([i,j]\) satisfies the conditions, then if we make \(i\) smaller or \(j\) larger, it still satisfies the conditions.”

When such a property holds, we can apply the algorithm called “sliding window”.
The sliding window technique is an algorithm of determining the sequence to search as follows:

• First, let \(L=R=1\).
• While \(L\) does not exceed \(M\), do the following.
  • (1) While the segment \([L,R]\) does not satisfy the conditions, add \(1\) to \(R\).
  • (2) Suppose that we found \([L,R]\) satisfying the conditions. Then, \([L,x]\) \((R\leq x \leq B)\) all satisfy the conditions, so add the count to the answer.
  • (3) Add \(1\) to \(L\). Then, if \(L\) does not exceed \(M\), go back to (1).

The key of the algorithm is that the segment expands and shrinks at most \(\mathrm{O}(M)\) times in total: the length of the segment changes when \(L\) or \(R\) increases by \(1\), which occurs at most \(2M\) times.

Therefore, the entire problem can be solved fast enough by expanding and shrinking the segment while checking if the segment satisfies the conditions. This can be achieved by managing “how many of \(A_i\) and \(B_i\) does \([L,R]\) contain?” for each \(1 \leq i \leq N\). (For more details, please refer to the implementation.)
The complexity is \(\mathrm{O}(N+M)\). The implementation follows.

#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];
  }
}