Day 23讲义：双指针，扫描线，区间覆盖，贪心

root 大佬 LV 3 SU · 2026-8-10 16:06:33

1. CF616D - Longest k-Good Segment

1.1 题目描述与问题抽象

给定一个长度为 $n$ 的正整数数组 $a$ 和一个正整数 $k$ 。定义一个连续子段 $[l, r]$ 是 $k$ -Good 的，当且仅当该子段中不同元素的数量不超过 $k$ 个。我们需要找出长度最长（即 $r - l + 1$ 最大）的 $k$ -Good 子段 $[l, r]$ （1-indexed），并输出其左右端点。若有多个最优解，输出任意一个即可。

数据范围： $1 \le k \le n \le 5 \times 10^5$ ， $0 \le a_i \le 10^6$ 。

1.2 核心思维推导与单调性分析

1. 朴素暴力的瓶颈

若暴力枚举所有可能的子段 $[l, r]$ （共 $O(n^2)$ 个），并对每个子段用 std::unordered_set 统计不同元素种类数（耗时 $O(r - l + 1)$ ），总时间复杂度高达 $O(n^3)$ 。即使用哈希表累加，也需要 $O(n^2)$ ，在 $n = 5 \times 10^5$ 时必然严重 TLE。

2. 窗口单调性（Monotonicity）

我们固定左端点 $l$ ，让右端点 $r$ 从 $l$ 开始逐渐向右延伸：

随着 $r$ 的右移，新元素被加入集合，区间 $[l, r]$ 包含的不同元素种类数 distinct_cnt 单调非递减。
如果当前区间 $[l, r]$ 中 distinct_cnt > k，那么对于任意 $r' > r$ ，区间 $[l, r']$ 的 distinct_cnt 也必定大于 $k$ 。
此时为了重新满足条件 distinct_cnt <= k，我们不需要将 $r$ 回溯，只需将左端点 $l$ 向右收缩。

这种“右端点扩展使指标单调增加，左端点收缩使指标单调减少”的性质，完全符合双指针（Sliding Window）的运行逻辑。

1.3 详细算法步骤

结构定义与初始化：

指针 $l = 1, r = 1$ 。
开辟全局频次数组 cnt[x]，记录当前窗口 $[l, r]$ 中数值 $x$ 出现的次数。
维护变量 distinct_cnt = 0，记录当前窗口内不同元素的种类数。
记录最优解 max_len = 0, best_l = 1, best_r = 1。

滑动窗口迭代：

右端点扩充：遍历 $r$ 从 $1$ 到 $n$ 。
检查 $a_r$ 在窗口中的频次：若 cnt[a_r] == 0，说明引入了新的不同数值，distinct_cnt 加 1。
更新频次：cnt[a_r]++。
左端点收缩：当 distinct_cnt > k 时，循环右移左端点 $l$ ：
cnt[a_l]--。
若 cnt[a_l] == 0，说明数值 $a_l$ 彻底离开了当前窗口，distinct_cnt 减 1。
$l$ 加 1。
记录答案：在调整完毕（满足 distinct_cnt <= k）后，当前窗口长度为 $len = r - l + 1$ 。若 $len > max\_len$ ，更新 $max\_len = len, best\_l = l, best\_r = r$ 。

1.4 复杂度分析

时间复杂度： $O(n)$ 。 $l$ 和 $r$ 指针在整个遍历过程中只单调递增，各自最多移动 $n$ 次。对于 cnt 数组的读写均在 $O(1)$ 时间内完成。
空间复杂度： $O(\max(a_i))$ 。需要开辟大小为 $\max(a_i) + 1 \approx 10^6 + 5$ 的频次数组。

2. CF1791F - Range Update Point Query

2.1 题目描述与问题抽象

给定一个长度为 $n$ 的正整数数组 $a$ ，需要支持 $q$ 次操作，包含以下两种类型：

1 l r：对区间 $[l, r]$ 内的所有元素 $a_i$ ，将其替换为其数位和（Sum of Digits）。
2 x：查询当前 $a_x$ 的实际数值。

数据范围： $1 \le t \le 10^4$ ， $1 \le n, q \le 2 \times 10^5$ ， $\sum n, \sum q \le 2 \times 10^5$ ， $1 \le a_i \le 10^9$ 。

2.2 核心数学性质：有限收敛性

本题最关键的打破点在于发现数值进行数位和替换后的衰减速度：

题目中 $a_i \le 10^9$ ，初始最大值为 $999,999,999$ 。
第 1 次变换： $a_i \to 9 \times 9 = 81$ 。
第 2 次变换： $81 \to 8 + 1 = 9$ 。
第 3 次变换： $9 \to 9$ 。

推论：任意一个处于 $[1, 10^9]$ 范围内的正整数，在经历最多 3 次数位和变换后，必然缩变为一位数（ $\le 9$ ）。一旦数值缩小到 9 以下，对其进行任何次数的数位和替换，其值将保持不变。

因此，对同一个位置执行超过 3 次有效替换是完全冗余的。

2.3 数据结构设计：树状数组差分 + 延迟懒算

1. 差分区间修改

既然修改操作是对区间 $[l, r]$ 内所有数执行“变换次数 $+1$ ”，我们可以使用树状数组（Fenwick Tree）维护差分数组：

当收到 1 l r 时，在树状数组上执行 range_add(l, r, 1)，即 add(l, 1) 与 add(r + 1, -1)。
这样，在 $O(\log n)$ 时间内就能完成区间的更新。

2. 单点查询与懒计算（Lazy Calculation）

维护一个数组 applied_times[x]，表示位置 $x$ 当前实际上已经被计算过了多少次数位和变换。
当收到 2 x 查询时：
通过树状数组的前缀和查询 query(x)，得到位置 $x$ 累计应当被修改的总次数 total_target_times。
只要 applied_times[x] < total_target_times 且当前 $a_x \ge 10$ ，我们就在单点查询时补算数位和：

$$a_x = \text{get\_digit\_sum}(a_x), \quad \text{applied\_times}[x]++$$

由于单点补算的上限是 3 次，所有查询在整个程序运行期间产生的单点补算开销累计不超过 $3n$ 次！

2.4 复杂度分析

时间复杂度：
区间更新 1 l r：单次 $O(\log n)$ 。
单点查询 2 x：树状数组查询 $O(\log n)$ ；单点补算全局累计最多 $O(n)$ 次，均摊单次 $O(1)$ 。
总时间复杂度为 $O((n + q) \log n)$ 。在 $\sum (n + q) \le 2 \times 10^5$ 限制下，运行时间 $< 0.08$ 秒。
空间复杂度： $O(n)$ ，只需额外的树状数组与 applied_times 数组。

3. CF1843E - Tracking Segments

3.1 题目描述与问题抽象

给定一个长度为 $n$ 的全 0 数组以及 $m$ 个固定区间 $[l_i, r_i]$ 。定义一个区间是“漂亮的（Beautiful）”，当且仅当该区间内 $1$ 的个数严格大于 $0$ 的个数。现顺次给出 $q$ 次单点修改（按顺序将位置 $x_k$ 置为 1，且位置不重复）。求最少需要执行前多少次修改，才能使得 $m$ 个区间中存在至少一个漂亮的区间。若执行完所有 $q$ 次修改仍无漂亮区间，输出 -1。

数据范围： $1 \le t \le 10^4$ ， $1 \le n, m, q \le 10^5$ ， $\sum n, \sum m, \sum q \le 2 \times 10^5$ 。

3.2 单调性推导与二分框架

1. 单调性（Monotonicity）

假设在执行了前 $k$ 次修改后，已经存在至少一个漂亮的区间。
当我们追加更多修改（即执行 $k' > k$ 次修改），由于修改只会把 $0$ 变成 $1$ ，任何已有的区间内 $1$ 的数量单调非递减， $0$ 的数量单调非递加。
因此，之前漂亮的区间在第 $k'$ 次修改后依然保持漂亮。
结论：“是否存在至少一个漂亮区间”这一命题关于修改次数 $k$ 具有严格的单调性。

2. 判定函数（Check Function）

对于一个给定的修改次数 $mid \in [1, q]$ ：

重构一个长度为 $n$ 的临时数组，将前 $mid$ 次修改对应的坐标位置赋值为 1，其余位置置为 0。
构造临时数组的前缀和 pref[i]，使得任意区间 $[l, r]$ 内 1 的个数能在 $O(1)$ 时间算得：

$$\text{count}_1 = \text{pref}[r] - \text{pref}[l - 1]$$

区间长度为 $len = r - l + 1$ 。该区间漂亮的充要条件是：

$$\text{count}_1 > \frac{len}{2} \iff \text{count}_1 \times 2 > len$$

顺序遍历所有 $m$ 个区间，若发现任意区间满足上述条件，即刻返回 true；若遍历完毕均不满足，返回 false。

3.3 复杂度分析

时间复杂度：
单次 Check 耗时：赋值 $O(mid) \le O(n)$ ，计算前缀和 $O(n)$ ，遍历区间 $O(m)$ ，单次 Check 总体为 $O(n + m)$ 。
二分范围为 $[1, q]$ ，二分轮数为 $\log_2 q$ 。
总体时间复杂度： $O((n + m) \log q)$ 。在 $\sum \le 2 \times 10^5$ 规模下，计算量仅 $\approx 3.6 \times 10^6$ 次，耗时 $< 0.05$ 秒。
空间复杂度： $O(n + m + q)$ 。

4. CF799C - Fountains

4.1 题目描述与问题抽象

有硬币预算 $C$ 和钻石预算 $D$ 。商店提供 $n$ 个喷泉，第 $i$ 个喷泉有美观度 $b_i$ 、价格 $p_i$ 和货币类型 $t_i$ （'C' 表示必须用硬币，'D' 表示必须用钻石）。我们必须选择恰好两个不同的喷泉购买，满足对应货币预算限制，使得选出的两个喷泉美观度之和最大。若无法合法选出两个喷泉，输出 0。

数据范围： $2 \le n \le 10^5$ ， $1 \le C, D \le 10^5$ ， $1 \le b_i, p_i \le 10^5$ 。

4.2 解空间完全分类讨论

挑选 2 个喷泉的组合，根据货币支付类型可以划分为互斥的三类：

情况 1：购买 1 个硬币喷泉 + 1 个钻石喷泉

两种货币预算互不干扰。
贪心策略：分别在所有成本 $p_i \le C$ 的硬币喷泉中选出 $b_i$ 最大的一个（记为 $max\_b_C$ ），在所有成本 $p_j \le D$ 的钻石喷泉中选出 $b_j$ 最大的一个（记为 $max\_b_D$ ）。
若两类均存在，则此情况的最大美观度为 $max\_b_C + max\_b_D$ 。

情况 2：购买 2 个硬币喷泉

需要选出两个不同的硬币喷泉 $i, j$ ，满足 $p_i + p_j \le C$ ，最大化 $b_i + b_j$ 。

情况 3：购买 2 个钻石喷泉

需要选出两个不同的钻石喷泉 $i, j$ ，满足 $p_i + p_j \le D$ ，最大化 $b_i + b_j$ 。

针对情况 2 和 3，我们需要解决同一个核心子问题：在一个喷泉集合中选出两个不同喷泉，使得价格和不超过 $MaxCost$ ，且美观度和最大。

4.3 核心子问题优化：前缀最大值 + 二分查找

对于同一种货币的喷泉集合：

将所有该类喷泉按价格 $p_i$ 从小到大排序。
构造前缀最大美观度数组 pref_max_b[i]：表示排序后下标在 $[0, i]$ 范围内的最大美观度 $b$ 。
遍历每一个喷泉 $i$ （作为两者中较贵的那个喷泉）：

剩余可用预算 $rem\_cost = MaxCost - p_i$ 。
若 $rem\_cost < \text{items}[0].cost$ ，说明连最便宜的另一个喷泉都买不起，直接跳过。
在候选范围 $[0, i - 1]$ 内，使用二分查找（upper_bound 思想）找到满足 $p_k \le rem\_cost$ 的最大下标 $k$ 。
则当前组合的最大美观度为 $b_i + \text{pref\_max\_b}[k]$ 。
遍历过程中持续更新全局最大值。

4.4 复杂度分析

时间复杂度：
情况 1 扫描： $O(n)$ 。
情况 2 与 3：排序开销 $O(n \log n)$ ，单次二分开销 $O(\log n)$ ，遍历二分总耗时 $O(n \log n)$ 。
总时间复杂度为 $O(n \log n)$ 。在 $n = 10^5$ 时，运行时间 $< 0.04$ 秒。
空间复杂度： $O(n)$ 。

5. CF1420D - Rescue Nibel!

5.1 题目描述与问题抽象

有 $n$ 个灯泡，第 $i$ 个灯泡在闭区间时间 $[l_i, r_i]$ 内处于开启状态。我们需要挑选出恰好 $k$ 个不同的灯泡，使得这 $k$ 个灯泡存在至少一个公共的重叠开启时刻（即这 $k$ 个区间的交集非空）。求符合条件的 $k$ 元组选择方案数，结果对 $998244353$ 取模。

数据范围： $1 \le k \le n \le 3 \times 10^5$ ， $1 \le l_i \le r_i \le 10^9$ 。

5.2 核心去重技巧：代表元素计数法

1. 扫描线事件化

将每个区间转换为两个事件点：

开灯事件：在时刻 $l_i$ 处，开启灯泡（标记为 $+1$ ）。
关灯事件：在时刻 $r_i + 1$ 处，关闭灯泡（标记为 $-1$ ）。将所有 $2n$ 个事件按时间排序。排序规则规定：时间相同时，先处理开灯事件，再处理关灯事件。

2. 多重计数的陷阱与解决方案

若在某个重叠时刻，当前有 $C$ 个灯泡同时亮着，直接简单累加 $\binom{C}{k}$ 会引发严重的重复统计。因为同一组 $k$ 个灯泡可能在连续的多个时刻同时亮着，会被重复计算多次。

为解决此问题，我们采用强制代表元素原理（Primary Element Principle）：

规约：当一个新的灯泡在时刻 $l_i$ 刚刚开启时，假设此时包含它在内，亮着的灯泡总数为 $C$ 。我们强制规定：在此刻产生的所有合法 $k$ 元组合中，必须包含这个刚刚开启的新灯泡！

由于组合中已经固定包含了这只刚开启的新灯泡，剩下的 $k - 1$ 个灯泡必须从之前已经亮着的 $C - 1$ 个灯泡中任意选择。因此，该新灯泡开启时刻产生的新增不重不漏的方案数恰好为：

\binom{C - 1}{k - 1}

我们只需要在扫描线推进的过程中，每当遇到一个开灯事件：

活跃计数 $C \gets C + 1$ 。
方案数加和：$\text{ans} = (\text{ans} + \binom{C - 1}{k - 1}) \pmod{998244353}$。遇到关灯事件： $C \gets C - 1$ 。

5.3 复杂度分析

时间复杂度：
事件排序： $2n$ 个事件排序耗时 $O(n \log n)$ 。
阶乘与逆元预处理： $O(n)$ 。
扫描线遍历： $2n$ 次循环，每次计算组合数 $O(1)$ ，总耗时 $O(n)$ 。
总体时间复杂度为 $O(n \log n)$ 。在 $n = 3 \times 10^5$ 规模下，耗时 $< 0.1$ 秒。
空间复杂度： $O(n)$ ，用于存储事件列表与预处理阶乘数组。

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

const int N = 6e5 + 10, Mod = 998244353;

struct Event {
	int time, type;
} e[N];

ll f[N], inf[N];

// 比较函数：按时间升序；相同时刻，优先处理开灯(+1)，再处理关灯(-1)
bool cmp(const Event &a, const Event &b) {
	if (a.time != b.time) return a.time < b.time;
	return a.type > b.type; // 1 (开灯) 优先于 -1 (关灯)
}

ll qmi(ll a, ll b, ll m) {
	ll ans = 1;
	while (b) {
		if (b & 1) ans = (ans * a) % m;
		a = (a * a) % m;
		b >>= 1;
	}
	return ans;
}

void init(int n) {
	f[0] = inf[0] = 1;
	for (int i = 1; i <= n; i++) {
		f[i] = f[i - 1] * i % Mod;
		inf[i] = inf[i - 1] * qmi(i, Mod - 2, Mod) % Mod;
	}
}

ll C(int n, int m) {
	if (m < 0 || m > n) return 0;
	return f[n] * inf[m] % Mod * inf[n - m] % Mod;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n, k;
	if (!(cin >> n >> k)) return 0;
	
	init(n);
	
	int tot = 0;
	for (int i = 1; i <= n; i++) {
		int l, r;
		cin >> l >> r;
		e[++tot] = {l, 1}; // 开灯
		e[++tot] = {r, -1}; // 关灯：由于先处理开灯，关灯时间戳设为 r 即可！
	}
	
	sort(e + 1, e + tot + 1, cmp);
	
	ll cnt = 0, ans = 0;
	for (int i = 1; i <= tot; i++) {
		if (e[i].type == 1) {
			cnt++;
			// 必须包含刚开启的这只灯，从剩下的 cnt-1 只中选 k-1 只
			ans = (ans + C(cnt - 1, k - 1)) % Mod;
		} else {
			cnt--;
		}
	}
	
	cout << ans << "\n";
	
	return 0;
}

6. CF1249D2 - Too Many Segments (hard version)

6.1. 题目大意

数轴上有 $n$ 个闭区间 $[l_i, r_i]$ 以及一个限制整数 $k$ 。如果数轴上的某个整数点 $x$ 被超过 $k$ 个区间覆盖，则称该点过度覆盖。

你需要删去数量最少的区间，使得数轴上的每一个点被覆盖的次数都不超过 $k$ 。输出最少删去的区间数以及被删去区间的原始编号（1-indexed）。

数据范围： $1 \le k \le n \le 2 \times 10^5$ ， $1 \le l_i \le r_i \le 2 \times 10^5$ 。

6.2. 核心算法与数据结构

核心思想：扫描线（Sweep Line）+ 贪心反悔（Greedy Elimination）
数据结构：std::set<pair<int, int>>（维护当前覆盖扫描点的活跃区间，存储 {右端点 r, 编号 id}）

6.3. 思路推导与数据结构选型

贪心策略

我们从左到右依次扫描坐标点 $x$ （从 $1$ 到 $\max(r_i)$ ）：

区间进场：将所有左端点 $l_i = x$ 的新区间加入当前活跃区间集合。
区间退场：所有右端点 $r_i < x$ 的区间已经无法覆盖点 $x$ ，将其从活跃集合中清除。
过度覆盖判定与处理：若当前覆盖点 $x$ 的活跃区间数量超过了 $k$ ，我们必须删去一部分区间。

应该删哪个？ 覆盖当前点 $x$ 的所有区间，其左端点都 $\le x$ 。它们唯一的区别是右端点 $r_i$ 。
右端点越靠右（越大）的区间，对未来（ $x$ 右侧）造成过度覆盖的潜在危害越大。
删掉 $r_i$ 最大的区间，能够在满足当前点限制的同时，最大程度减轻后续坐标点的覆盖压力。

为什么必须用 `std::set`？（对比大顶堆）

这道题数据结构选型的核心考点在于：活跃集合需要同时支持“清理过期最小值”和“贪心获取最大值”。

数据结构	清理过期区间 ( $r < x$ )	贪心获取最大区间	为什么不行 / 为什么可以
大顶堆 `priority_queue`	只能检查堆顶	堆顶即最大值	❌ 会 WA。过期区间 $r < x$ 属于较小值，会被深压在大顶堆底部。若堆顶有合法大区间挡着，堆底的过期区间无法被弹出，导致 `q.size()` 虚高，误删合法区间。
`std::set`	头部 `s.begin()` 即最小值	尾部 `prev(s.end())` 即最大值	✅ 完美 AC。`set` 内部始终升序有序，从头部能 100% 彻底清空所有 $r < x$ 的过期区间，保证 `s.size()` 绝对真实，随后从尾部切掉 $r$ 最大的区间。

4. 详细算法步骤

预处理：用 vector 静态数组 head[l] 存储所有以 $l$ 为左端点的区间 {r, id}，同时记录最大的右端点 max_r。
扫描线推进：遍历点 $i$ 从 $1$ 到 max_r：

进场：遍历 head[i]，将所有以 $i$ 启动的区间 s.insert({r, id}) 放入 set。
退场：检查 s.begin()，只要 s.begin()->first < i，就不断 s.erase(s.begin())，彻底清空过期区间。
超限处理：当 (int)s.size() > k 时，取出 auto it = prev(s.end())（即 $r$ 最大的区间），记录答案 ans[++ans_cnt] = it->second，并在 set 中删掉该区间 s.erase(it)。

输出：输出删去的总数 ans_cnt 以及对应的区间编号。

5. 复杂度分析

时间复杂度： $O(N \log N)$
每个区间最多入 set 一次，最多出 set 一次。
set 的插入与删除单次均为 $O(\log N)$ 。
坐标扫描线上限为 $2 \times 10^5$ ，总计算量仅约 $3.6 \times 10^6$ 次，能在 0.05 秒 内极速 AC。
空间复杂度： $O(N)$
head 数组与 set 的最大元素量均不超过 $N$ 。

6.4 复杂度分析

时间复杂度：
分组预处理： $O(n)$ 。
扫描线遍历：坐标轴范围最大为 $2 \times 10^5$ 。每个区间最多入堆 1 次，出堆 1 次，单次堆操作 $O(\log n)$ 。
总时间复杂度为 $O(n \log n)$ 。运行时间 $< 0.05$ 秒。
空间复杂度： $O(n + \max(r_i))$ 。

6.5 规范代码实现 (GDY C++ Style)

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

const int N = 2e5 + 10;

// head[l] 存储以 l 为左端点的区间 {r, id}
vector<pair<int, int>> head[N];
// 维护当前活跃的区间集合 {r, id}，自动按 r 从小到大排序
set<pair<int, int>> s;

int ans[N], ans_cnt;

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

	int n, k;
	if (!(cin >> n >> k)) return 0;

	int max_r = 0;
	for (int i = 1; i <= n; i++) {
		int l, r;
		cin >> l >> r;
		head[l].push_back({r, i});
		max_r = max(max_r, r);
	}

	for (int i = 1; i <= max_r; i++) {
		// 1. 左端点为 i 的区间进场
		for (auto &item : head[i]) {
			s.insert(item);
		}

		// 2. 右端点小于 i 的区间退场 (清理 set 头部最小值)
		while (!s.empty() && s.begin()->first < i) {
			s.erase(s.begin());
		}

		// 3. 覆盖超限：删右端点最远的 (弹出 set 尾部最大值)
		while ((int)s.size() > k) {
			auto it = prev(s.end());
			ans[++ans_cnt] = it->second;
			s.erase(it);
		}
	}

	cout << ans_cnt << "\n";
	for (int i = 1; i <= ans_cnt; i++) {
		cout << ans[i] << (i == ans_cnt ? "" : " ");
	}
	cout << "\n";

	return 0;
}

7. 全题目综合对比与解题思维阵型

题目	算法分类	核心思想 / 不变量	经典数据结构	复杂度
A	双指针 / 滑动窗口	窗口单调性：右扩增加种类，左缩减少种类	数组 HashMap	$O(n)$
B	数学收敛 + 数据结构	有限收敛性：数位和最多 3 次收敛至一位数	树状数组 (BIT)	$O((n+q)\log n)$
C	二分答案 + 区间查询	单调性判定：修改增加使漂亮区间存续单调	静态前缀和	$O((n+m)\log q)$
D	分类讨论 + 前缀最值	解空间正交化划分 + 维度固定	前缀 Max 数组 / 二分	$O(n \log n)$
E	扫描线 + 组合计数	强制代表元素去重：组合必定包含最新开灯者	阶乘逆元数组
F	扫描线 + 反悔贪心	贪心撤销：过度覆盖时优先撤销右端点最远者	优先队列（大顶堆）

已修改 7 次查看举报