题解 | #小sun的假期#

本题要求计算 $N$ 天安排中，最长的连续无安排（即放假）天数。由于总天数 $N$ 可能非常大（导致直接用数组标记会内存超限），但安排数量 $M$ 相对较小，因此我们采用事件点（扫描线）结合差分思想来解决此问题，将复杂度从依赖 $N$ 降到依赖 $M$ 。

核心思想：关注变化点

传统的差分数组需要长度为 $N$ 的数组来记录每一天的状态变化，适用于 $N$ 较小的情况。当 $N$ 很大时，我们不再关注每一天，而是只关注状态发生变化的关键时间点。

一个安排 $[l, r]$ 会导致两个关键状态变化：

在第 $l$ 天，状态从“可能放假”变为“有安排”（覆盖数 +1）。
在第 $r+1$ 天，状态从“有安排”变回“可能放假”（覆盖数 -1）。

通过收集并排序这些关键时间点，我们沿着时间轴进行“扫描”，在两个相邻事件点之间，覆盖状态是恒定的，从而可以计算出这段时间内的放假天数。

算法步骤

1. 收集事件点

我们使用一个 std::map<long long, int> (或 std::vector + 排序) 来存储事件点，其中 key 是时间，value 是状态变化量（ $+1$ 或 $-1$ ）。

对于输入的每个安排 $[l, r]$ ：
- 在时间 $l$ 处记录状态变化 $+1$ 。
- 在时间 $r+1$ 处记录状态变化 $-1$ 。

2. 扫描并计算（前缀和）

由于 std::map 会自动根据 key（时间）进行排序，我们只需遍历 map，模拟时间轴上的扫描过程。

初始化：
- max_happiness = 0 (最大快乐值)。
- current_coverage = 0 (当前天数被安排覆盖的次数，即前缀和)。
- last_time = 1 (上一个事件点的时间，初始为第一天)。
遍历事件点：
- 设当前事件点时间为 $T$ ，状态变化为 $C$ 。
- 计算区间快乐值： 在时间轴上，从 last_time 到 $T-1$ 的这段时间，覆盖状态保持为上一个 current_coverage。
  - 如果上一个 current_coverage 为 $0$ (即放假状态)： $\text{放假天数} = T - \text{last\_time}$ 用此天数更新 max_happiness。
- 更新状态： current_coverage += C。
- 更新时间： last_time = T。

3. 处理末尾区间

遍历结束后，还需要检查从最后一个事件点 last_time 到总天数 $N$ 结束的这段区间。

如果此时 current_coverage 仍为 $0$ 且 $\text{last_time} \le N$ ： $\text{末尾放假天数} = N - \text{last\_time} + 1$
如果没有任何安排 ( $M=0$ )，max_happiness 应为 $N$ 。

复杂度分析

假设 $N$ 是总天数， $M$ 是安排数量。

步骤	时间复杂度	空间复杂度	备注
1. 收集事件点	$O(M \log M)$	$O(M)$	`std::map` 或 `std::vector` 排序所需的时间和空间。
2. 扫描计算	$O(M)$	$O(1)$	遍历 $2M$ 个事件点。
总计	$\mathbf{O(M \log M)}$	$\mathbf{O(M)}$	算法效率只与安排数量 $M$ 相关，成功解决了 $N$ 很大时的内存超限问题。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

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

    long long n;
    int m;
    cin >> n >> m;

    map<long long, int> events;

    for (int k = 0; k < m; ++k) {
        long long l, r;
        cin >> l >> r;

        if (l <= n) {
            events[l]++;
        }

        if (r + 1 <= n + 1) {
            events[r + 1]--;
        }
    }

    long long max_happiness = 0;
    long long current_coverage = 0;
    long long last_time = 1;

    for (const auto& pair : events) {
        long long current_time = pair.first;
        int change = pair.second;

        if (current_coverage == 0) {
            long long holiday_duration = current_time - last_time;
            max_happiness = max(max_happiness, holiday_duration);
        }

        current_coverage += change;

        last_time = current_time;
    }

    if (current_coverage == 0 && last_time <= n) {
        long long holiday_duration = n - last_time + 1;
        max_happiness = max(max_happiness, holiday_duration);
    }

    if (events.empty()) {
        max_happiness = n;
    }

    cout << max_happiness << endl;

    return 0;
}