rt。

#include <bits/stdc++.h>

using namespace std;
int n, m;
array<bitset<64>, 10001> a;

inline pair<int, int> foo(int pos) {
    return {pos >> 6, pos & 0x3f};
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> m;
    for (int i = 0; i <= foo(n).first; ++i) {
        a[i].set();
    }
    for (int i = 0; i < m; ++i) {
        int l, r;
        cin >> l >> r;
        l--, r--;
        auto x = foo(l), y = foo(r);
        if (x.first != y.first) {
            for (int j = x.second; j < 64; ++j) {
                a[x.first].reset(j);
            }
            for (int j = x.first + 1; j < y.first; ++j) {
                a[j].reset();
            }
            for (int j = y.second; j >= 0; --j) {
                a[y.first].reset(j);
            }
        } else {
            for (int j = x.second; j <= y.second; ++j) {
                a[x.first].reset(j);
            }
        }
        int ans = 0;
        for (int j = 0; j < foo(n).first; ++j) {
            ans += a[j].count();
        }
        for (int j = 0; j < foo(n).second; ++j) {
            if (a[foo(n).first][j]) {
                ans++;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

压位之后常数/=64，最大的点在300ms左右。 为了方便用了bitset。