- Conference (会议安排)

复杂度 $O(n\log n)$，可直接通过 $n \le 2 \times 10^5$。

一、

1. 问题转化

我们需要统计所有连续区间 $[L,R]$，满足： 可以给每一天分配一个不同的、当天有空的讲师。

这是一个二分图完美匹配问题。

2. 霍尔定理（Hall 定理）

$[L,R]$ 合法 $\iff$ 对其中任意天数子集 $S$，能覆盖的讲师数 $\ge |S|$。

3. 核心问题

直接检查所有子集不可能，且非法子集可以不连续（如 $\{1,3\}$）。

4. 官方核心变换

对所有讲师的区间 $[l_i,r_i]$ 做变换：

• 如果有多个讲师 $l_i$ 相同
• 保留一个，其余的 $l_i \gets l_i+1$
• 直到 所有 $l_i$ 互不相同

此变换不改变答案。

5. 变换后超强结论

变换后： 一个区间 $[L,R]$ 合法 $\iff$ 它自身满足 Hall 条件 不需要检查任何子区间！

6. 最终合法条件

将所有区间按 $l_i$ 从小到大排序。 对长度 $k=R-L+1$：

且

7. 双指针统计

用双指针找到所有合法 $[L,R]$，最后按长度统计答案。

二、AC 代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAX = 2e5 + 10;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    vector<pair<int, int>> seg(n);
    for (auto& p : seg) cin >> p.first >> p.second;

    // ======================
    // 步骤1：标程变换 l_i 去重
    // ======================
    sort(seg.begin(), seg.end());
    vector<pair<int, int>> res;
    priority_queue<int, vector<int>, greater<int>> pq;

    int ptr = 0;
    for (int x = 1; x <= 2e5; x++) {
        while (ptr < n && seg[ptr].first == x) {
            pq.push(seg[ptr].second);
            ptr++;
        }
        while (!pq.empty()) {
            int r = pq.top();
            pq.pop();
            res.emplace_back(x, r);
            break; // 只保留一个，其余 l+1
        }
    }

    // 有效区间
    vector<pair<int, int>> arr;
    for (auto& p : res) {
        if (p.first <= p.second) arr.push_back(p);
    }
    int m = arr.size();

    // ======================
    // 步骤2：按 l 排序，预处理后缀 min
    // ======================
    sort(arr.begin(), arr.end());
    vector<int> min_r(m + 1, 2e5 + 10);
    for (int i = m - 1; i >= 0; i--) {
        min_r[i] = min(arr[i].second, min_r[i + 1]);
    }

    // ======================
    // 步骤3：双指针统计合法区间
    // ======================
    vector<ll> ans(n + 2, 0);
    int j = 0;

    for (int i = 0; i < m; i++) {
        j = max(j, i);
        while (j < m && min_r[i] >= arr[j].first) {
            j++;
        }
        int L = arr[i].first;
        int R = arr[j - 1].first;
        int len = j - i;
        if (len > n) continue;
        ans[len] += (R - L + 1);
    }

    // ======================
    // 输出答案
    // ======================
    for (int k = 1; k <= n; k++) {
        cout << ans[k] << " ";
    }
    cout << endl;

    return 0;
}

三、代码结构

1. 变换去重 $l_i$ 标程核心变换，保证所有 $l_i$ 唯一。

2. 排序 按 $l_i$ 从小到大。

3. 预处理 $\min r$ 用于快速判断 Hall 条件。

4. 双指针扫描 统计所有合法区间。

5. 按长度输出答案 对 $k=1\dots n$ 输出方案数。

四、复杂度

• 变换：$O(n\log n)$
• 排序：$O(n\log n)$
• 双指针：$O(n)$
• 总复杂度：$O(n\log n)$