题目重述

我们有 $n$ 个时刻（步骤），$m$ 只猫，第 $i$ 只猫在时间段 $[l_i, r_i]$ 内出现。
在每个时刻，我们可以选择“喂食所有当前在场的猫”或者“什么都不做”。
不能有猫被喂超过一次。
目标：最大化被喂过的猫的数量。

等价形式：
选择若干个时刻（喂食时刻），使得 没有一条给定的区间包含两个或更多选中的时刻，并且 被选中的时刻覆盖的区间数量 最大。

---

思路分析

这是一道 动态规划 + 贪心 的问题。

1. 关键观察

如果我们选择在时刻 $i$ 喂食，那么所有在 $i$ 时刻在场的猫都会被喂一次。
这些猫的出现区间都包含 $i$。
那么，这些区间的 左端点的最小值 记为 $L$，则所有左端点 $\ge L$ 且 $\le i$ 且右端点 $\ge i$ 的猫都在此时被喂。
更关键的是：
如果我们在 $i$ 时刻喂食，那么上一次喂食的时刻必须 严格小于 $L$，否则 $L$ 对应的猫会被喂两次（因为它的区间包含 $i$ 和上一个喂食点）。

因此：

• 设 $first[i]$ 表示所有覆盖时刻 $i$ 的区间中，最小的左端点。
• 如果在 $i$ 时刻喂食，则上一次喂食必须在 $first[i] - 1$ 或更早。

---

2. 状态定义

设 $dp[i]$ 表示考虑前 $i$ 个时刻（即时刻 $1$ 到 $i$），能够喂食的猫的最大数量。

---

3. 转移方程

情况 1：不在时刻 $i$ 喂食

那么 $dp[i] = dp[i-1]$（直接继承前 $i-1$ 个时刻的最优解）。

情况 2：在时刻 $i$ 喂食

此时，设 $x = first[i]$ 为覆盖 $i$ 的所有区间的最小左端点。
那么在时刻 $i$ 喂食时，所有满足 $l \le i \le r$ 的猫都会被喂一次。
但我们必须保证上一次喂食时刻 $< x$，否则 $x$ 对应的猫会重复喂。

同时，所有覆盖 $i$ 的猫中，有些可能左端点 $< x$？不可能，因为 $x$ 是最小左端点，所以所有覆盖 $i$ 的猫的左端点都 $\ge x$，并且 $\le i$。
因此，在时刻 $i$ 喂食时，能喂到的猫的数量 = 覆盖 $i$ 的区间数量，记为 $cnt[i]$。

于是：

$$dp[i] = \max(dp[i],\ dp[x-1] + cnt[i])$$

---

4. 如何计算 $first[i]$ 和 $cnt[i]$？

我们可以通过预处理实现：

• 用 op[l] 表示以 $l$ 为左端点的区间数量（即时刻 $l$ 有多少只猫开始出现）。
• 用 del[r] 存储所有以 $r$ 为右端点的区间的左端点。

然后从左到右扫描时刻 $i$：

• 将时刻 $i$ 开始的所有区间加入一个有序集合 cur（这里存的是左端点）。
• 此时 cur 中所有元素的左端点 $\le i$，且右端点 $\ge i$（因为我们还没删除结束的区间）。
  所以 cur 的大小就是 $cnt[i]$，cur 中的最小值就是 $first[i]$。
• 然后处理 del[i]，即删除所有右端点为 $i$ 的区间（它们的左端点从 cur 中移除）。

---

5. 算法步骤

1. 读入 $n, m$ 以及所有区间 $[l, r]$。
2. 初始化 op[l]++ 和 del[r].push_back(l)。
3. 初始化 dp[0] = 0，一个空的多重集合 cur。
4. 对于 $i = 1$ 到 $n$：
   • 将 $i$ 插入 cur 共 op[i] 次（表示这些区间开始）。
   • 令 $dp[i] = dp[i-1]$（不喂食）。
   • 如果 cur 非空：
     • 令 $first = *cur.begin()$（最小左端点）。
     • $cnt = cur.size()$。
     • 更新 $dp[i] = \max(dp[i], dp[first-1] + cnt)$。
   • 遍历 del[i] 中的每个左端点 $l$，从 cur 中删除一个 $l$。
5. 输出 $dp[n]$。

---

6. 时间复杂度

• 每个区间在开始时插入一次，结束时删除一次，$O(m \log m)$。
• 扫描 $n$ 个时刻，每个时刻常数操作。
• 总复杂度 $O(n + m \log m)$，足够通过。

---

标程代码注释版

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

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> op(n + 1);               // op[l] = 以 l 为左端点的区间数
    vector<vector<int>> del(n + 1);      // del[r] 存储所有以 r 为右端点的左端点
    for (int i = 0; i < m; ++i) {
        int l, r;
        cin >> l >> r;
        op[l]++;
        del[r].push_back(l);
    }

    multiset<int> cur;                   // 存储当前覆盖的区间的左端点
    vector<int> dp(n + 1, 0);

    for (int i = 1; i <= n; ++i) {
        // 加入所有以 i 为左端点的区间
        for (int j = 0; j < op[i]; ++j) {
            cur.insert(i);
        }

        // 不喂 i
        dp[i] = dp[i - 1];

        // 喂 i
        if (!cur.empty()) {
            int first = *cur.begin();    // 覆盖 i 的最小区间左端点
            int cnt = cur.size();        // 覆盖 i 的区间数量
            dp[i] = max(dp[i], dp[first - 1] + cnt);
        }

        // 删除所有以 i 为右端点的区间
        for (int l : del[i]) {
            cur.erase(cur.find(l));
        }
    }

    cout << dp[n] << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

---

举例验证

以第一个样例：

15 6
2 10
3 5
2 4
7 7
8 12
11 11

手动模拟：

• 在 $i=4$ 时，覆盖 $4$ 的区间有 $[2,10],[3,5],[2,4]$，最小左端点 $first=2$，$cnt=3$。
  $dp[4] = \max(dp[3], dp[1]+3) = \max(0, 0+3)=3$。
• 在 $i=11$ 时，覆盖 $11$ 的区间有 $[8,12],[11,11]$，$first=8$，$cnt=2$。
  $dp[11] = \max(dp[10], dp[7]+2)$。
  最终得到 $dp[15]=5$。

---

总结

本题核心：

• 将问题转化为选择喂食时刻，保证每个区间至多包含一个选中的时刻。
• 用 $dp[i]$ 表示前 $i$ 个时刻的最优解。
• 在时刻 $i$ 喂食时，利用覆盖 $i$ 的所有区间的最小左端点来限制前一次喂食时刻。
• 通过扫描线和 multiset 动态维护 $cnt[i]$ 和 $first[i]$。

这种 DP + 扫描线 + 数据结构 的方法在区间选择类问题中非常经典。