考虑题目可以看成天和人的匹配，因此判断单个日期区间 \([l, r]\) 可以考虑 Hall 定理，设 \(N(S)\) 为在 \(S\) 这些天有空的人的数量，定义 \(S\) 合法当且仅当 \(|N(S)| \ge |S|\)，那么 \([l, r]\) 合法当且仅当 \(\forall S \subseteq [l, r]\)，\(S\) 合法。
猜测只用 check 形成一段区间的 \(S\)，但是会被下面的数据叉掉：
3
1 3
2 2
2 2
对于 \([1, 3]\)，只有 \(\{1, 3\}\) 不合法。
因此考虑对初始的线段进行一些处理。发现对于两条线段 \([a, b]\) 和 \([a, c]\)（其中 \(b \le c\)），把它们换成 \([a, b], [a + 1, c]\) 不影响结果（特别地，若 \(a = b = c\) 则相当于删去 \([a, c]\) 这条线段）。这部分实现可以扫描线，枚举 \(l\)，把最小且 \(\ge l\) 的右端点 \(r\) 和 \(l\) 形成的线段 \([l, r]\) 加入。
处理后每个人的线段的左端点互不相同，这时候就只用 check 形成一段区间的 \(S\) 了，因为若 \(|N(S)| < |S|\) 且 \(\exists x, y \in S\) 使得 \([x + 1, y - 1]\) 都不属于 \(S\)，那么加入 \([x + 1, y - 1]\) 后 \(|N(S)| < |S|\) 仍然满足，因为每加一个数 \(|N(S)|\) 至多增加 \(1\)。
所以此时不合法区间满足单调性，即若 \([l, r]\) 不合法，那么 \([l - 1, r], [l, r + 1]\) 都不合法。
所以可以双指针求出，对于每个 \(l\) 最大的 \(r\)，使得 \([l, r]\) 合法（\([l, r + 1]\) 不合法）。
最后差分统计一下即可。
时间复杂度 \(O((n + V) \log n)\)。
code
// Problem: F. Conference
// Contest: Codeforces - Codeforces Round 941 (Div. 1)
// URL: https://codeforces.com/problemset/problem/1965/F
// Memory Limit: 512 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
ll n, m, b[maxn], c[maxn], d[maxn], ans[maxn];
vector<ll> vc[maxn];
struct node {
ll l, r;
node(ll a = 0, ll b = 0) : l(a), r(b) {}
} a[maxn];
void solve() {
scanf("%lld", &n);
ll nn = n;
for (int i = 1; i <= n; ++i) {
scanf("%lld%lld", &a[i].l, &a[i].r);
m = max(m, a[i].r);
}
priority_queue< ll, vector<ll>, greater<ll> > pq;
for (int i = 1; i <= n; ++i) {
vc[a[i].l].pb(a[i].r);
}
n = 0;
for (int i = 1; i <= m; ++i) {
for (int j : vc[i]) {
pq.push(j);
}
while (pq.size() && pq.top() < i) {
pq.pop();
}
if (pq.size()) {
a[++n] = node(i, pq.top());
pq.pop();
}
}
for (int i = 1; i <= n; ++i) {
b[a[i].l] = a[i].r;
++c[a[i].r];
++d[a[i].l];
--d[a[i].r + 1];
}
int s = 0;
for (int i = m, j = m; i; --i) {
s += c[i];
while (j >= i && s < j - i + 1) {
s -= (b[j] ? 1 : 0);
--j;
}
if (j <= m) {
++ans[j - i + 1];
}
}
for (int i = max(m, nn); i; --i) {
ans[i] += ans[i + 1];
}
for (int i = 1; i <= nn; ++i) {
printf("%lld\n", ans[i]);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}