8.10总结

T1 Longest k-Good Segment

链接:Longest k-Good Segment - 题目详情 - QY code

题意

给定一个长度为 $n$ 的整数数组 $a$，定义连续子段（segment）为数组中一个或多个连续的元素。如果一个连续子段中包含的不同元素个数不超过 $k$ 个，则称这个子段为 k-good 子段。

请你找出任意一个最长的 k-good 子段，输出它的左右端点下标（从 1 开始编号）。

---

思路

算法选择：双指针（滑动窗口）

这是一道经典的「最多包含 k 个不同元素的最长子数组」问题，标准解法是双指针（滑动窗口），时间复杂度 $O(n)$。

核心思想

维护一个窗口 $[l, r]$，始终保证窗口内不同元素的个数 $\le k$：

1. **右指针 **$r$ 不断向右扩展，将新元素加入窗口
2. 如果加入新元素后，窗口内不同元素个数 **超过 $k$，则不断向右移动左指针 **$l$，缩小窗口，直到不同元素个数重新 $\le k$
3. 在每次窗口合法时，更新最长子段的答案

数据结构

使用哈希表（unordered_map）统计窗口内每个元素的出现次数：

• cnt[x] 表示元素 $x$ 在当前窗口中的出现次数
• diff 表示窗口中不同元素的个数

具体步骤

1. 初始化 $l = 0$，diff = 0，最大长度 maxLen = 0，答案端点 ansL = ansR = 0

2. 遍历 $r$ 从 $0$ 到 $n-1$：

   • 如果 cnt[a[r]] == 0，说明这是一个新元素，diff++

    - cnt[a[r]]++（计数加1）

    - 当 diff > k 时：循环移动左指针 $l$

      - cnt[a[l]]--（计数减1）

      - 如果 cnt[a[l]] == 0，说明该元素已完全移出窗口，diff--

      - $l++$

    - 此时窗口 $[l, r]$ 合法，如果 $r-l+1 > maxLen$，更新答案

3. 最终输出 ansL + 1 和 ansR + 1（转为 1-based 下标）

复杂度分析

• 时间复杂度：$O(n)$

  - 右指针 $r$ 遍历一次数组（$n$ 步）

  - 左指针 $l$ 最多也移动 $n$ 次（不会超过 $r$）

  - 每个元素最多被加入和移出窗口各一次，均摊 $O(1)$

• 空间复杂度：$O(n)$

  - 最坏情况下（所有元素都不同），哈希表中存储 $n$ 个键值对

---

代码关键点

1. 快速 I/O：题目提示数据量较大，使用 scanf/printf 代替 cin/cout 以避免超时
2. 1-based 输出：代码中使用 0-based 下标处理，输出时记得 +1
3. unordered_map** vs **map：优先使用 unordered_map（平均 $O(1)$ 访问），如果担心哈希冲突可以改用 map（$O(\log n)$），但对于本题 $5 \times 10^5$ 的数据量，两者都能通过

代码

#include <bits/stdc++.h> 
using namespace std;
int main () {
    int n, k;
    scanf ("%d%d", &n, &k);
    vector <int> a (n + 1);
	for (int i = 1; i <= n; i++) scanf ("%d", &a[i]);
    unordered_map <int, int> cnt;
    int l = 1;
    int diff = 0;
    int maxLen = 0;
    int ansL = 0, ansR = 0;
    for (int r = 1; r <= n; r++) {
        if (cnt[a[r]] == 0) diff ++;
        cnt[a[r]] ++;
        while (diff > k) {
            cnt[a[l]]--;
            if (cnt[a[l]] == 0) diff --;
            l++;
        }
        if (r - l + 1 > maxLen) {
            maxLen = r - l + 1;
            ansL = l;
            ansR = r;
        }
    }
    printf("%d %d", ansL, ansR);
    return 0;
}

T2 Range Update Point Query

链接：Range Update Point Query - 题目详情 - QY code

题意

给定长度为 $n$ 的数组 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），需要处理 $q$ 次操作：

• 操作1 1 l r：对区间 $[l, r]$ 内的每个元素 $a_i$，将其替换为 $a_i$ 的数位和（各位数字之和）。

  - 例：$a_i = 1434 \to 1+4+3+4 = 12$

• 操作2 2 x：输出当前位置 $a_x$ 的值。

数据范围

• $1 \le t \le 1000$（测试组数）
• $1 \le n, q \le 2 \times 10^5$，所有组 $n$ 之和、$q$ 之和均 $\le 2 \times 10^5$
• $1 \le a_i \le 10^9$

---

思路

1. 暴力做法的问题

操作1要求对区间内每个元素取数位和，如果每次都遍历 $[l, r]$ 逐个修改，最坏情况 $O(nq)$，会超时。

2. 关键观察：数位和快速收敛

一个数不断取数位和，会极快收敛到个位数：

| 起始值范围 | 取 1 次后 | 取 2 次后 | 取 3 次后 |

|-----------|----------|----------|----------|

| $\le 9$（个位数） | 不变 | 不变 | 不变 |

| $\le 81$（如 79） | $\le 16$ | $\le 9$（个位数） | 不变 |

| $\le 10^9$（如 999999999） | $\le 81$ | $\le 9$（个位数） | 不变 |

结论：任何 $\le 10^9$ 的数，最多取 2 次数位和就变成个位数，取 3 次一定够了。

3. 关键性质：幂等性 + 确定性

• 幂等性：个位数的数位和 = 自身，再多取也不变
• 确定性：数位和是一个确定的函数 $f(x)$，对原始值取 $c$ 次 $= f^c(a_x)$，与中间过程无关

这意味着：不需要真正修改数组，只需记录每个位置被"操作1"覆盖了多少次，查询时从原始值出发，套 $\min(c, 3)$ 次数位和即可。

4. 树状数组：差分维护更新次数

树状数组天然支持区间加 + 单点查询（差分思想）：

差分原理

维护差分数组 $d$，其中 $d[i] = \text{位置 } i \text{ 的更新次数}$ 的差分：

• 区间更新 $[l, r]$ 加 1：add(l, +1)，add(r+1, -1)

  - 这样位置 $l$ 到 $r$ 的前缀和各 $+1$，位置 $r+1$ 之后不变

• **单点查询 **$x$：query(x) = 前缀和 $\sum_{i=1}^{x} d[i]$ = 位置 $x$ 被更新的总次数

5. 正确性证明

需要证明：从原始值套 min(c, 3) 次数位和 = 逐次套 c 次数位和的实际结果

• **当 **$c \le 3$：$\min(c, 3) = c$，直接套 $c$ 次，显然正确。
• **当 **$c > 3$：原始值 $\le 10^9$，套 2 次必成个位数，套 3 次也一定是个位数。第 4 次及之后取数位和不改变值。所以套 3 次 = 套 $c$ 次，$\min(c, 3) = 3$ 正确。

6. 复杂度分析

| 操作 | 时间复杂度 |

|------|-----------|

| 区间更新（操作1） | $O(\log n)$ — 两次 add |

| 单点查询（操作2） | $O(\log n)$ — 一次 query + 最多 3 次 digitSum（每次 $O(\log a_i)$，常数级） |

| 总计 | $O((n + q) \log n)$ |

空间复杂度：$O(n)$（树状数组 + 原数组）

---

代码注意事项

1. tree** 数组清零**：每组测试数据开头，将 tree[1..n] 清零。由于 n 每组不同，只需清当前范围即可，不需要全量 memset。
2. r+1** 越界保护**：当 $r = n$ 时，add(r+1, -1) 会访问 tree[n+1]，需用 if (r+1 <= n) 跳过。
3. 数据类型：$a_i \le 10^9$，用 long long 存储更稳妥，scanf 用 %lld。

---

与 set 解法对比

|---|---------|------------|

| 核心思路 | 用 set 维护仍 > 9 的下标，区间更新时只处理有效元素，直接修改数组 | 用树状数组记录每个位置的更新次数，查询时从原始值延迟计算 |

| 是否修改原数组 | 是，每次更新直接改 $a[i]$ | 否，原数组始终保持初始值 |

| 区间更新复杂度 | 均摊 $O(\log n)$（每个元素最多处理 3 次） | 严格 $O(\log n)$（两次差分 add） |

| 单点查询复杂度 | $O(1)$（直接读数组） | $O(\log n)$（前缀查询 + 3 次数位和） |

| 实现难度 | 中等（需处理 set 迭代器删除） | 较简单（标准 BIT 模板） |

| 适用场景 | 需要"跳过无效元素"的通用模式 | 操作具有幂等性 / 收敛性时可延迟计算 |

两种解法总复杂度都是 $O((n+q) \log n)$，树状数组解法胜在代码简洁、逻辑清晰，set 解法胜在单点查询 O(1)。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, q;
int tree[200010];
void add (int i, int v) {
    for (; i <= n; i += i & (-i)) tree[i] += v;
}
int query (int i) {
    int s = 0;
    for (; i > 0; i -= i & (-i)) s += tree[i];
    return s;
}
int getans (ll x) {
    int s = 0;
    while (x) {
        s += x % 10;
        x /= 10;
    }
    return s;
}
int main () {
	int T;
    scanf ("%d", &T);
    while (T--) {
        scanf ("%d%d", &n, &q);
        vector <ll> a (n + 1);
        for (int i = 1; i <= n; i++) {
            scanf ("%lld", &a[i]);
            tree[i] = 0;
        }
        while (q--) {
            int op;
            scanf ("%d", &op);
            if (op == 1) {
                int l, r;
                scanf ("%d%d", &l, &r);
                add (l, 1);
                if (r + 1 <= n) add (r + 1, -1);
            }
            else {
                int x;
                scanf ("%d", &x);
                int c = min (query (x), 3);
                ll ans = a[x];
                for (int i = 0; i < c; i++) ans = getans (ans);
                printf ("%lld\n", ans);
            }
        }
    }
	return 0;
}

树状数组代码比set简单多了

T3 Tracking Segments

链接：Tracking Segments - 题目详情 - QY code

题意

给定一个长度为 $n$ 的全 0 数组 $a$，以及 $m$ 个区间 $[l_i, r_i]$。

然后依次执行 $q$ 次修改，第 $j$ 次修改将 $a_{x_j}$ 设为 $1$（所有 $x_j$ 互不相同）。

定义区间 $[l_i, r_i]$ 为漂亮的当且仅当该区间内 1 的个数 严格大于 0 的个数。

求：最早在第几次修改之后，至少有一个区间变为漂亮的。如果始终没有，输出 $-1$。

数据范围

• $1 \le t \le 10^4$，所有测试组 $n$ 之和 $\le 10^5$
• $1 \le m \le n \le 10^5$，$1 \le q \le n$

---

思路

1. 关键观察：单调性

随着修改次数增加，数组中的 1 只会越来越多，0 越来越少。因此：

• 如果某个区间在第 $k$ 次修改后变为漂亮的，那么第 $k+1, k+2, \dots$ 次后它仍然是漂亮的
• "是否存在漂亮区间"这个性质是单调的：一旦为真，永远为真

2. 二分答案

由于单调性，可以二分求最小的修改次数 $mid$：

• 二分范围：$lo = 1$，$hi = q$
• 判定：执行前 $mid$ 次修改后，是否存在至少一个漂亮区间

  - 若存在：答案 $\le mid$，继续往左找（$hi = mid - 1$）

  - 若不存在：答案 $> mid$，往右找（$lo = mid + 1$）

3. 判定函数

给定 $mid$，判断前 $mid$ 次修改后是否存在漂亮区间：

1. 将前 $mid$ 次修改的位置标记为 1，其余为 0

2. 构建前缀和数组 $pre$，$pre[i]$ 表示前 $i$ 个位置中 1 的个数

3. 对每个区间 $[l_i, r_i]$：

   • 1 的个数 = $pre[r_i] - pre[l_i - 1]$

    - 0 的个数 = 区间长度 $- 1$ 的个数 = $(r_i - l_i + 1) - \text{ones}$

    - 漂亮条件：$\text{ones} > \text{zeros}$，即 $2 \times \text{ones} > r_i - l_i + 1$

4. 只要有一个区间满足，判定为真

4. 复杂度分析

• 每次判定：$O(n + m)$（构建前缀和 $O(n)$ + 检查 $m$ 个区间 $O(m)$）
• 二分次数：$O(\log q)$
• 总计：$O((n + m) \log q)$

---

代码

#include <bits/stdc++.h>
using namespace std;
int main () {
    int T;
    scanf ("%d", &T);
    while (T--) {
        int n, m;
        scanf ("%d%d", &n, &m);
        vector <int> L (m + 1), R (m + 1);
        for (int i = 1; i <= m; i++) scanf ("%d%d", &L[i], &R[i]);
        int q;
        scanf ("%d", &q);
        vector <int> x (q + 1);
        for (int i = 1; i <= q; i++) scanf ("%d", &x[i]);
        int l = 1, r = q, ans = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            vector <int> pre (n + 1, 0);
            for (int i = 1; i <= mid; i++) pre[x[i]] = 1;
            for (int i = 1; i <= n; i++) pre[i] += pre[i - 1];
            bool flag = false;
            for (int i = 1; i <= m; i++) {
                int ones = pre[R[i]] - pre[L[i] - 1];
                int len = R[i] - L[i] + 1;
                if (2 * ones > len) {
                    flag = true;
                    break;
                }
            }
            if (flag) {
                ans = mid;
                r = mid - 1;
            }
            else l = mid + 1;
        }
        printf ("%d\n", ans);
    }
    return 0;
}

T4：Fountains

链接：Fountains - 题目详情 - QY code

这道题其实就是分类讨论+二分，跟模拟没啥区别，只是加了点小优化，所以直接贴个代码吧

#include <bits/stdc++.h>
using namespace std;
int main () {
    int n, c, d;
    scanf ("%d%d%d", &n, &c, &d);
    vector <pair <int, int> > cf, df;
    cf.push_back ({0, 0});
    df.push_back ({0, 0});
    for (int i = 1; i <= n; i++) {
        int b, p;
        char t;
        scanf ("%d%d %c", &b, &p, &t);
        if (t == 'C') cf.push_back ({p, b});
        else df.push_back ({p, b});
    }
    int ans = 0;
    sort (cf.begin () + 1, cf.end ());
    int kc = cf.size () - 1;
    if (kc >= 2) {
        vector <int> p (kc + 1), b (kc + 1);
        for (int i = 1; i <= kc; i++) {
            p[i] = cf[i].first;
            b[i] = cf[i].second;
        }
        vector <int> mx (kc + 1), sec (kc + 1), mxidx (kc + 1);
        mx[1] = b[1], sec[1] = 0, mxidx[1] = 1;
        for (int i = 2; i <= kc; i++) {
            if (b[i] > mx[i - 1]) {
                sec[i] = mx[i - 1];
                mx[i] = b[i];
                mxidx[i] = i;
            }
            else if (b[i] > sec[i - 1]) {
                sec[i] = b[i];
                mx[i] = mx[i - 1];
                mxidx[i] = mxidx[i - 1];
            }
            else {
                mx[i] = mx[i - 1];
                sec[i] = sec[i - 1];
                mxidx[i] = mxidx[i - 1];
            }
        }
        for (int i = 1; i <= kc; i++) {
            if (p[i] > c) break;
            int rem = c - p[i];
            int l = 1, r = kc, j = -1;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (p[mid] <= rem) {
                    j = mid;
                    l = mid + 1;
                }
                else r = mid - 1;
            }
            if (j < 0) continue;
            int best;
            if (mxidx[j] != i) best = mx[j];
            else best = sec[j];
            if (best > 0) ans = max (ans, b[i] + best);
        }
    }
    sort (df.begin () + 1, df.end ());
    int kd = df.size () - 1;
    if (kd >= 2) {
        vector <int> p (kd + 1), b (kd + 1);
        for (int i = 1; i <= kd; i++) {
            p[i] = df[i].first;
            b[i] = df[i].second;
        }
        vector <int> mx (kd + 1), sec (kd + 1), mxidx (kd + 1);
        mx[1] = b[1], sec[1] = 0, mxidx[1] = 1;
        for (int i = 2; i <= kd; i++) {
            if (b[i] > mx[i - 1]) {
                sec[i] = mx[i - 1];
                mx[i] = b[i];
                mxidx[i] = i;
            }
            else if (b[i] > sec[i - 1]) {
                sec[i] = b[i];
                mx[i] = mx[i - 1];
                mxidx[i] = mxidx[i - 1];
            }
            else {
                mx[i] = mx[i - 1];
                mxidx[i] = mxidx[i - 1];
                sec[i] = sec[i - 1];
            }
        }
        for (int i = 1; i <= kd; i++) {
            if (p[i] > d) break;
            int rem = d - p[i];
            int l = 1, r = kd, j = -1;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (p[mid] <= rem) {
                    j = mid;
                    l = mid + 1;
                }
                else r = mid - 1;
            }
            if (j < 0) continue;
            int best;
            if (mxidx[j] != i) best = mx[j];
            else best = sec[j];
            if (best > 0) ans = max (ans, b[i] + best);
        }
    }
    int mc = 0, md = 0;
    for (int i = 1; i <= kc; i++) {
        if (cf[i].first <= c) mc = max (mc, cf[i].second);
    }
    for (int i = 1; i <= kd; i++) {
        if (df[i].first <= d) md = max (md, df[i].second);
    }
    if (mc && md) ans = max (ans, mc + md);
    printf ("%d", ans);
    return 0;
}

就是代码出错率太高了，我调了很久

T5 Rescue Nibel!

链接：Rescue Nibel! - 题目详情 - QY code

题目大意

有 $n$ 盏灯，每盏灯在时间区间 $[l_i, r_i]$ 内亮着。要求选出 $k$ 盏灯，使得存在某一时刻这 $k$ 盏灯同时亮着。问有多少种选法，答案对 $998244353$ 取模。

核心思想：扫描线 + 组合计数

1. 事件建模

将每盏灯的开启和关闭看作两个事件：

| 事件类型 | 含义 | 表示 |

|---------|------|------|

| 开灯事件 | 灯在时刻 $l$ 亮起 | $(l, 0)$ |

| 关灯事件 | 灯在时刻 $r$ 熄灭 | $(r, 1)$ |

将所有事件按时间从小到大排序。若时间相同，开灯事件 (0) 排在关灯事件 (1) 前面——这样做是为了正确处理边界：例如一盏灯在时刻 $t$ 开启，另一盏灯在时刻 $t$ 关闭，排序后先处理开启再处理关闭，保证两盏灯在时刻 $t$ 算作同时亮着（符合 $[l_i, r_i]$ 闭区间的语义）。

2. 扫描过程

用一个计数器 cnt 记录当前同时亮着的灯的数量：

• 遇到开灯事件：cnt++
• 遇到关灯事件：cnt--

3. 关键计数公式

当处理一盏灯的开灯事件后，若 cnt >= k，则答案增加：

$ans \leftarrow ans + \binom{cnt - 1}{k - 1}$

为什么是 $\binom{cnt-1}{k-1}$？

当一盏新灯在时刻 $t$ 亮起时（cnt 变为某个值），在它之前已经有 cnt-1 盏灯亮着。从这 cnt-1 盏灯中任选 k-1 盏，与当前这盏灯一起就构成了一个 $k$ 盏灯的集合，它们在时刻 $t$ 同时亮着。

$\binom{cnt-1}{k-1}$ 恰好等于「以当前这盏灯作为 $k$ 盏中最后一个亮起的灯」的选法数。

4. 为什么不会重复计数？

这是整个算法最精妙的地方。

对于任意一个满足条件的 $k$ 盏灯的集合，它们的所有 $l_i$ 存在一个最大值 $l_{\max}$。在事件序列中，这个集合只会在那台具有 $l_{\max}$ 的灯的开灯事件处被计数一次。

• 若有多盏灯同时在 $l_{\max}$ 时刻开启（即它们的 $l$ 值相同且都是最大值），则集合会在第一台这样的灯的开灯事件处被计数。因为当处理第一台时，其余 $k-1$ 台灯（包括其他同 $l$ 值的灯）都已经亮着了（在同一时间点先处理了开灯事件）。

这样每个合法的 $k$ 集合恰好被计数一次，不会重复。

复杂度分析

| 项目 | 复杂度 |

|------|--------|

| 时间 | $O(n \log n)$（排序） |

| 空间 | $O(n)$（事件数组 + 阶乘数组） |

关键总结

1. 事件建模：将区间问题转化为事件问题，是处理「区间交集」的经典技巧
2. 排序策略：同时间点上开灯 (0) 优先于关灯 (1)，保证边界正确
3. 组合计数：$\binom{cnt-1}{k-1}$ 避免重复计数——每个合法 $k$ 集合仅在其「最晚开灯的那台灯」处被计数一次
4. 模逆元预处理：利用费马小定理 $O(n)$ 预处理逆元，$O(1)$ 查询组合数

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 998244353;
ll power (ll a, ll b, ll mod) {
    ll res = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
ll fact[300010];
ll ifact[300010];
void init (int n) {
    fact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;
    ifact[n] = power (fact[n], MOD - 2, MOD);
    for (int i = n - 1; i >= 0; i--) ifact[i] = ifact[i + 1] * (i + 1) % MOD;
}
ll C (int n, int r) {
    if (r < 0 || r > n) return 0;
    return fact[n] * ifact[r] % MOD * ifact[n - r] % MOD;
}
int main () {
    int n, k;
    scanf ("%d%d", &n, &k);
    init (n);
    vector <pair <int, int> > a;
    for (int i = 1; i <= n; i++) {
        int l, r;
        scanf ("%d%d", &l, &r);
        a.push_back ({l, 0});
        a.push_back ({r, 1});
    }
    sort (a.begin (), a.end ());
    long long ans = 0;
    int cnt = 0;
    for (int i = 0; i < (int)a.size (); i++) {
        if (a[i].second == 0) {
            cnt ++;
            if (cnt >= k) ans = (ans + C (cnt - 1, k - 1)) % MOD;
        }
        else cnt --;
    }
    printf ("%lld", ans);
    return 0;
}

T6：Too Many Segments (hard version)

链接：Too Many Segments (hard version) - 题目详情 - QY code

题意概述

给定 n 条线段，若某个整数点被超过 k 条线段覆盖，则称其为"坏点"。要求移除最少的线段，使得不存在坏点。

• 输入：n, k 以及 n 条线段的端点 l_i, r_i
• 输出：最少移除线段数 m 和被移除线段的编号

思路：贪心 + 有序集合（multiset）

核心思想

按左端点 l 从小到大依次处理每条线段，维护一个按右端点 r 升序排列的 multiset，存储当前"活跃"的线段（即与当前扫描位置有重叠的线段）。

当活跃线段数超过 k 时，贪心策略：移除右端点 r 最大的那条线段（集合末尾元素）。原因是：右端点越大，该线段覆盖的范围越广，与后续线段产生冲突的可能性最大，因此优先移除它最划算。

为什么用 multiset 而非 priority_queue

使用 priority_queue（最大堆）时，堆中只能高效获取堆顶元素（右端点 r 最大的）。这导致一个问题：过期的线段（r < 当前 l）如果 r 较大，会阻塞在堆顶，使得更小 r 的过期线段无法被清理，从而使堆大小虚高，引发不必要的删除操作。

multiset 则能同时支持：

• 从集合头部（r 最小）高效清理过期线段：(*active.begin ()).first < cur_l 判断后 active.erase (active.begin ())
• 从集合尾部（r 最大）高效移除冲突线段：*active.rbegin () 取出末尾元素，再用 active.find (last) 定位并 active.erase () 删除

两者均为 O(log n)，保证集合大小始终反映真实的活跃线段数量。

算法步骤

1. 排序：将所有线段按左端点 l 升序排序

2. 逐段扫描：对于每条线段：

   • 清理过期线段：从集合头部依次弹出 r < 当前 l 的线段（这些线段已结束）

    - 加入集合：将当前线段 (r, idx) 插入 multiset

    - 处理超限：若集合大小 > k，从尾部取出 r 最大的线段并移除

复杂度分析

• 排序：O(n log n)
• multiset 操作：每条线段最多插入一次、删除一次，每次操作 O(log n)，共 O(n log n)
• 总体：O(n log n)，满足 n ≤ 2×10^5 的要求

代码关键点

1. multiset 排序规则：pair <int, int> 默认按 first（右端点 r）升序排列，begin () 为 r 最小元素，rbegin () 为 r 最大元素
2. 过期清理条件：r < cur_l 而非 r <= cur_l，因为线段端点处仍有重叠（如 [7,8] 和 [8,9] 在点 8 处重叠）
3. 无需惰性删除：multiset 可以直接从头部删除过期元素，无需标记已移除状态
4. 尾部取值用 rbegin：*active.rbegin () 取 r 最大的元素值，再通过 active.find (last) 定位后 erase 删除，无需显式声明迭代器

代码

#include <bits/stdc++.h>
using namespace std;
struct Seg {
    int l, r, idx;
};
bool cmp (Seg a, Seg b) {
    return a.l < b.l;
}
int main () {
    int n, k;
    scanf ("%d%d", &n, &k);
    vector <Seg> segs (n);
    for (int i = 0; i < n; i++) {
        scanf ("%d%d", &segs[i].l, &segs[i].r);
        segs[i].idx = i + 1;
    }
    sort (segs.begin (), segs.end (), cmp);
    multiset <pair <int, int> > active;
    vector <int> ans;
    for (int i = 0; i < n; i++) {
        int cur_l = segs[i].l;
        while (!active.empty () && (*active.begin ()).first < cur_l) {
            active.erase (active.begin ());
        }
        active.insert (make_pair (segs[i].r, segs[i].idx));
        while ((int)active.size () > k) {
            pair <int, int> last = *active.rbegin ();
            ans.push_back (last.second);
            active.erase (active.find (last));
        }
    }
    printf ("%d\n", (int)ans.size ());
    for (int i = 0; i < (int)ans.size (); i++) {
        if (i > 0) printf (" ");
        printf ("%d", ans[i]);
    }
    if (!ans.empty ()) printf ("\n");
    return 0;
}