基础算法与 STL
这是所有算法题的地基。STL 用熟之后，你的写题速度会有质的飞跃——很多原本要手写几十行的东西，STL 一行搞定。
从 STL 军火库，到排序二分（含二分答案）、前缀和差分、双指针、贪心、递归分治、栈队列单调结构——这些是你后续每一道题都要反复用到的工具。把它们练成肌肉记忆，把脑力留给真正的算法本身。
1.1 STL 精通
进入第一部分：基础算法与 STL。这是所有算法题的地基，STL 用熟之后，你的写题速度会有质的飞跃——很多原本要手写几十行的东西，STL 一行搞定。
先建立一个核心认知：
STL 是你的「军火库」。 竞赛里 90% 的数据存储和操作，都不用自己手写，直接调 STL。把这十来个容器和函数用成肌肉记忆，你就能把脑力全部留给算法本身。
我按使用频率讲，前四个（vector / sort / pair / 二分）是每道题都可能用的，必须滚瓜烂熟；后面几个（set / map / 优先队列 / 栈队列）是特定场景的利器。
一、vector —— 会变长的数组（最常用，必须精通）
vector 就是「能自动改变大小的数组」，是你用得最多的容器。
vector<int> v; // 空的 int 数组
vector<int> v(n); // n 个元素，初值都是 0
vector<int> v(n, -1); // n 个元素，初值都是 -1
vector<int> v = {1, 2, 3}; // 直接初始化核心操作（背下来）：
v.push_back(x); // 末尾加一个元素 x（最常用）
v.pop_back(); // 删除末尾元素
v.size(); // 元素个数
v.empty(); // 是否为空
v[i]; // 下标访问，和普通数组一样
v.back(); // 最后一个元素
v.front(); // 第一个元素
v.clear(); // 清空（多测时常用！）遍历的两种写法：
// 写法1：下标遍历（要用到下标时用这个）
for (int i = 0; i < v.size(); i++) cout << v[i] << " ";
// 写法2：范围 for（只读取值、不要下标时，更简洁）
for (int x : v) cout << x << " ";
// 要修改元素时，范围 for 加引用 &
for (int &x : v) x *= 2; // 把每个元素翻倍二维 vector（动态二维数组，比固定数组灵活，不易 MLE）：
vector<vector<int>> g(n); // n 行，每行是空的 vector（存图常用）
vector<vector<int>> a(n, vector<int>(m, 0)); // n×m 的二维数组，初值 0
g[u].push_back(v); // 第 u 行末尾加 v（邻接表存图就这么干）vector 高频用途：存输入的数组、存图的邻接表、动态收集一批数据。多测时记得
clear()或重新定义（接 0.3）。
二、sort —— 排序（每道题都可能用）
排序是竞赛最高频的操作，sort 一行搞定，默认从小到大：
sort(v.begin(), v.end()); // vector 从小到大
sort(a, a + n); // 普通数组 a[0..n-1] 从小到大从大到小两种写法：
sort(v.begin(), v.end(), greater<int>()); // 写法1：传 greater
// 或者排完再翻转
sort(v.begin(), v.end());
reverse(v.begin(), v.end()); // 写法2：先升序再 reverse自定义排序规则（极重要）——用 cmp 函数或 lambda 定义「谁排前面」：
// 比如对结构体按某个字段排序
struct Node { int x, y; };
vector<Node> a;
// 按 x 从小到大排
sort(a.begin(), a.end(), [](Node p, Node q) {
return p.x < q.x; // 返回 true 表示 p 排在 q 前面
});
// 按 x 从小到大，x 相同按 y 从大到小（双关键字）
sort(a.begin(), a.end(), [](Node p, Node q) {
if (p.x != q.x) return p.x < q.x; // 先比 x，小的在前
return p.y > q.y; // x 相同，y 大的在前
});记忆要诀：cmp 函数 return a < b 就是升序（小的在前），return a > b 就是降序。return 的条件 = 「a 应该排在 b 前面的条件」。
[](...){...}是 lambda（匿名函数），写在 sort 里很方便，不用单独定义函数。这个语法记住模板照抄即可。
三、pair —— 把两个值绑一起（高频）
pair 就是「一对值打包」，常用来存坐标、存「权值+编号」、存边等。
pair<int, int> p = {3, 5}; // 一对 int
p.first; // 第一个值：3
p.second; // 第二个值：5
// 也可以用 make_pair 构造
pair<int, int> p = make_pair(3, 5);pair 的排序很特殊（重点）：pair 默认先按 first 排，first 相同再按 second 排。这个特性超好用：
vector<pair<int, int>> v;
v.push_back({3, 1});
v.push_back({1, 5});
v.push_back({1, 2});
sort(v.begin(), v.end());
// 结果：{1,2}, {1,5}, {3,1} —— 先按 first，first 相同按 second经典用法：要「按权值排序但还想知道原来的编号」时，存 pair<权值, 编号>，排序后 first 是权值、second 是编号，编号自动跟着走：
vector<pair<int, int>> a;
for (int i = 0; i < n; i++) {
int x; cin >> x;
a.push_back({x, i}); // {值, 原下标}
}
sort(a.begin(), a.end()); // 按值排序，原下标自动跟随存三个值用
pair<int, pair<int,int>>也行，但更建议用结构体（更清晰）。坐标、边权这类两元组，pair 最方便。
四、二分查找 —— lower_bound / upper_bound（高频，易错）
在已排序的容器里快速查找，O(log n)。前提：数据必须先排好序！
lower_bound(begin, end, x)：找第一个 ≥ x 的位置upper_bound(begin, end, x)：找第一个 > x 的位置
它们返回的是迭代器（指针），要减去起始位置才能得到下标：
vector<int> v = {1, 3, 3, 5, 7}; // 必须已排序
// 找第一个 >= 3 的位置
int pos = lower_bound(v.begin(), v.end(), 3) - v.begin();
// pos = 1（v[1]=3 是第一个 >=3 的）
// 找第一个 > 3 的位置
int pos2 = upper_bound(v.begin(), v.end(), 3) - v.begin();
// pos2 = 3（v[3]=5 是第一个 >3 的）常见应用：
// 1. 查 x 在不在数组里
int pos = lower_bound(v.begin(), v.end(), x) - v.begin();
if (pos < v.size() && v[pos] == x) cout << "找到了，下标 " << pos;
else cout << "不存在";
// 2. 统计等于 x 的元素有几个
int cnt = upper_bound(v.begin(), v.end(), x) - lower_bound(v.begin(), v.end(), x);
// 3. 统计 <= x 的元素有几个
int cnt = upper_bound(v.begin(), v.end(), x) - v.begin();易错点：① 必须先排序，没排序结果是错的；② 返回的是迭代器，记得
- v.begin()转成下标；③ 数组版写lower_bound(a, a+n, x) - a。
五、set —— 自动排序 + 自动去重的集合
set 存的元素自动从小到大排序、自动去重（重复的只留一个）。增删查都是 O(log n)。
set<int> s;
s.insert(3); // 插入
s.insert(1);
s.insert(3); // 重复，无效（自动去重）
// 此时 s = {1, 3}，自动有序
s.erase(1); // 删除元素 1
s.count(3); // 查 3 在不在（返回 0 或 1）
s.size(); // 元素个数
// 遍历（自动升序）
for (int x : s) cout << x << " ";查找是否存在：
if (s.count(x)) ... // x 存在
if (s.find(x) != s.end()) ... // 同样意思，find 返回迭代器set 用途：需要「维护一个有序、不重复的集合，还要频繁增删查」时用。如果允许重复元素，用
multiset。如果不需要有序、只要去重和查存在，unordered_set更快（O(1)）。小心：set 不能用下标
s[i]访问！它不是数组。要按顺序访问只能遍历。
六、map —— 键值对映射（超高频）
map 是「键 → 值」的映射，可以用任意类型当下标（key），自动按 key 排序。最常用来计数、建立对应关系。
map<string, int> mp; // 字符串 → 整数 的映射
mp["apple"] = 5; // 像数组一样用，但下标可以是字符串
mp["banana"] = 3;
cout << mp["apple"]; // 输出 5
// 计数神器：统计每个数出现几次
map<int, int> cnt;
for (int i = 0; i < n; i++) {
int x; cin >> x;
cnt[x]++; // x 出现次数 +1（不存在时自动初始化为 0 再 +1）
}关键操作：
mp.count(key); // key 在不在（返回 0 或 1）
mp.find(key); // 返回迭代器
mp.erase(key); // 删除
mp.size(); // 键值对数量
// 遍历（按 key 自动升序）
for (auto [k, v] : mp) cout << k << " -> " << v << "\n";
// 老写法：for (auto it : mp) cout << it.first << " -> " << it.second;map 最经典的用途是计数和映射：「统计每个元素出现次数」「把名字映射到编号」「记录某个值有没有出现过」。
重要陷阱：
mp[key]这个操作，如果 key 不存在，会自动创建它并赋默认值 0！所以if (mp[x] == 0)这种写法会意外创建一堆元素。只想查存在用mp.count(x)，别用mp[x]。效率：map 的操作是 O(log n)（带个 log）。如果不需要 key 有序、只要映射和计数，用
unordered_map（平均 O(1)，更快）。铜牌阶段 map 一般够用，数据大且卡常时换 unordered_map。
七、priority_queue —— 优先队列（堆）
priority_queue 是「优先队列」，能随时取出当前最大（或最小）的元素，O(log n)。常用于贪心、Dijkstra 最短路等。
// 默认大根堆：堆顶是最大值
priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(5);
pq.top(); // 取堆顶（最大值）：5
pq.pop(); // 弹出堆顶
pq.size();
pq.empty();小根堆（堆顶是最小值，更常用，比如 Dijkstra）——记住这个又长又必须背的写法：
priority_queue<int, vector<int>, greater<int>> pq; // 小根堆，堆顶最小存 pair（按 first 比较，Dijkstra 标配）：
// 小根堆存 {距离, 节点}，自动按距离从小到大出队
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
pq.push({dist, node});
auto [d, u] = pq.top(); // 取出距离最小的priority_queue 用途：每次都要「取当前最值」的场景。贪心题（每次选最大/最小）、Dijkstra（每次取距离最近的点）、合并果子类问题。
记忆技巧：大根堆是默认（
priority_queue<int>），小根堆要加vector<int>, greater<int>。小根堆那串太长，建议存到你的模板里随时复制。
八、stack 和 queue —— 栈和队列
stack（栈）：后进先出（LIFO），像叠盘子，最后放的最先拿。
stack<int> st;
st.push(x); // 入栈
st.top(); // 看栈顶
st.pop(); // 出栈
st.empty();
st.size();queue（队列）：先进先出（FIFO），像排队，先来的先走。BFS 必用。
queue<int> q;
q.push(x); // 入队（队尾）
q.front(); // 看队首
q.pop(); // 出队（队首）
q.empty();
q.size();用途：stack 用于括号匹配、单调栈、表达式求值、DFS 的非递归实现；queue 用于 BFS（广度优先搜索）、滑动窗口。这两个后面搜索专题（第二部分）会大量用到。
九、其他实用函数（零碎但好用）
max(a, b); min(a, b); // 最大/最小值
max({a, b, c}); // 多个数的最大值（注意花括号）
swap(a, b); // 交换两个变量
reverse(v.begin(), v.end()); // 翻转
abs(x); fabs(x); // 整数绝对值 / 浮点绝对值
__gcd(a, b); // 最大公约数（内置函数，数论常用）
unique(v.begin(), v.end()); // 去重（需先排序，配合 erase 用）
// 去重的完整写法（离散化常用）
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end()); // 排序后去掉相邻重复十、本节速记卡（你的 STL 速查表）
| 容器/函数 | 干什么 | 关键操作 | 典型场景 |
|---|---|---|---|
| vector | 变长数组 | push_back size [i] clear | 存数组、邻接表 |
| sort | 排序 | sort(v.begin(),v.end()) + cmp | 几乎每题 |
| pair | 绑两个值 | .first .second | 坐标、值+编号 |
| lower_bound | 二分找位置 | -v.begin() 转下标 | 有序数组查找 |
| set | 有序去重集合 | insert count erase | 维护有序不重复 |
| map | 键值映射 | mp[key] count | 计数、建映射 |
| priority_queue | 堆，取最值 | push top pop | 贪心、Dijkstra |
| stack/queue | 栈/队列 | push top/front pop | DFS/BFS |
学习建议：这些不要死背，要在做题中练熟。我的建议是——前四个（vector / sort / pair / 二分）你这两天就要用到完全不假思索的程度；后面的 set / map / 优先队列，在遇到对应题型时重点练。map 计数、priority_queue 小根堆、lower_bound 转下标这三个是最容易写错又最常用的，多写几遍形成肌肉记忆。
要不要我出一组专练 STL 的题（比如用 map 计数、用 pair+sort 排序、用 lower_bound 查找、用优先队列贪心，每个考点一两道）让你立刻盘活这些工具？还是直接往下讲 1.2 排序与二分（含「二分答案」这个铜牌高频技巧）？
配套练习题
好，给你 6 道题，每道精准对应一个 STL 考点，难度从易到中。这组题的目标是把刚学的 vector / map / pair+sort / lower_bound / set / priority_queue 全部盘活成肌肉记忆。
老规矩：先自己写，写完再展开对照。 重点不是做出来，而是把对应的 STL 工具用顺手。
第 1 题：词频统计（练 map 计数 —— 最高频用法）
题意：给你 n 个单词，统计每个单词出现的次数，然后按字典序输出每个单词和它的次数。
输入样例
6
apple banana apple cherry banana apple
输出样例
apple 3
banana 2
cherry 1考点：map<string,int> 计数 + map 自动按 key 升序的特性（输出时不用手动排序）。
AC第 1 题 参考（map 计数）▸
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
map<string, int> cnt;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
cnt[s]++; // 计数核心：不存在自动建 0 再 +1
}
for (auto [word, c] : cnt) { // map 遍历自动按 key 升序
cout << word << " " << c << "\n";
}
return 0;
}要点：cnt[s]++ 是 map 计数的标准写法。输出时不用 sort，因为 map 本身就按 key（字典序）排好了——这就是用 map 而非 unordered_map 的好处。
第 2 题：成绩排序（练 pair + sort 双关键字）
题意：n 个学生，每人有学号（输入顺序 1~n）和分数。按分数从高到低排序输出学号；分数相同的，学号小的排前面。
输入样例
4
90 85 90 70
输出样例
1 3 2 4（学号1和3都是90分，学号小的1在前；然后是85分的2号，最后70分的4号）
考点：pair<int,int> 存 {分数, 学号}，自定义 cmp 实现「分数降序、学号升序」的双关键字排序。
AC第 2 题 参考（pair + 双关键字 sort）▸
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<pair<int, int>> a; // {分数, 学号}
for (int i = 1; i <= n; i++) {
int score;
cin >> score;
a.push_back({score, i});
}
sort(a.begin(), a.end(), [](pair<int,int> p, pair<int,int> q) {
if (p.first != q.first) return p.first > q.first; // 分数降序
return p.second < q.second; // 分数同，学号升序
});
for (auto [score, id] : a) cout << id << " ";
cout << "\n";
return 0;
}要点：cmp 里 p.first > q.first 是降序（分数高的在前），p.second < q.second 是升序（学号小的在前）。双关键字就是「先比第一个，相等再比第二个」。
第 3 题：查找元素位置（练 lower_bound 二分查找）
题意：给一个有 n 个整数的数组（已经从小到大排好序），再给 q 次询问，每次问一个数 x 是否在数组中。在就输出它的下标（从 0 开始，如果有重复输出第一个），不在输出 -1。
输入样例
5
1 3 3 5 7
3
3
4
7
输出样例
1
-1
4考点：lower_bound 找位置 + 判断是否真的等于 x（0.4/1.1 强调的那个易错点：找到位置还要验证值相等）。
AC第 3 题 参考（lower_bound）▸
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i]; // 已排序
int q;
cin >> q;
while (q--) {
int x;
cin >> x;
int pos = lower_bound(a.begin(), a.end(), x) - a.begin();
if (pos < n && a[pos] == x) cout << pos << "\n"; // 必须验证 a[pos]==x
else cout << -1 << "\n";
}
return 0;
}要点：lower_bound 找到的是「第一个 ≥ x 的位置」，但这个位置的值不一定等于 x（x 可能根本不存在）。所以必须加 pos < n && a[pos] == x 双重判断——先确保没越界，再确认值相等。这是 lower_bound 最容易翻车的地方。
第 4 题：去重输出（练 set 自动去重排序）
题意：给 n 个整数，去掉重复的，然后从小到大输出剩下的不同的数。
输入样例
7
3 1 4 1 5 9 3
输出样例
1 3 4 5 9考点：set<int> 一插入就自动去重 + 自动有序，遍历直接输出。（也可以用 vector + sort + unique，两种都写写对比一下。）
AC第 4 题 参考（set 去重）▸
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
set<int> s;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
s.insert(x); // 自动去重 + 自动排序
}
for (int x : s) cout << x << " ";
cout << "\n";
return 0;
}对比写法（vector + sort + unique）：
vector<int> v(n);
for (int i = 0; i < n; i++) cin >> v[i];
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end()); // 去重三件套
for (int x : v) cout << x << " ";要点：set 写法最简洁。但记住 vector+sort+unique 这套，因为离散化（后面会遇到）就靠它，而且数据量大时它比 set 快。
第 5 题：合并果子（练 priority_queue 小根堆 —— 经典贪心）
题意：有 n 堆果子，第 i 堆有 a[i] 个。每次可以把两堆合并成一堆，消耗的体力等于这两堆果子数之和。要把所有果子合成一堆，问最少消耗多少体力。
输入样例
3
1 2 9
输出样例
15（先合并最小的两堆 1+2=3 消耗3，剩下 {3, 9}；再合 3+9=12 消耗12；总共 3+12=15）
考点：贪心策略「每次合并最小的两堆」→ 用小根堆每次取出两个最小值，合并后再放回堆。这是 priority_queue 小根堆的经典应用题，务必掌握。
提示：注意答案可能很大，用 long long（接 0.2 溢出意识）。
AC第 5 题 参考（priority_queue 小根堆）▸
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
priority_queue<long long, vector<long long>, greater<long long>> pq; // 小根堆
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
pq.push(x);
}
long long ans = 0;
while (pq.size() > 1) { // 直到只剩一堆
long long a = pq.top(); pq.pop(); // 最小的两堆
long long b = pq.top(); pq.pop();
ans += a + b; // 消耗 = 两堆之和
pq.push(a + b); // 合并后放回
}
cout << ans << "\n";
return 0;
}要点：① 小根堆的声明 priority_queue<long long, vector<long long>, greater<long long>>，那串 greater 必须记住；② 每次取两个最小、合并、放回，循环到只剩一个；③ 答案累加可能很大，全程 long long（合并体力总和容易超 int）。这道是小根堆的模板题，建议背下来。
第 6 题：数字配对（练 map 查存在 —— 两数之和）
题意：给 n 个整数和一个目标值 k，问数组中有多少对数 (i, j)（i < j）满足 a[i] + a[j] == k。
输入样例
5 6
1 5 3 3 2
输出样例
2（满足的对：1+5=6，3+3=6，共 2 对）
考点：用 map 边遍历边记录「之前每个数出现了几次」，遍历到 x 时查 k-x 出现过几次累加。这是把 O(n²) 暴力优化成 O(n) 的经典套路（接 0.7 复杂度思维）。
下面是参考答案，自己写完再看：
AC第 6 题 参考（map 查存在 / 两数之和）▸
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
long long k;
cin >> n >> k;
map<long long, int> cnt; // 记录每个数之前出现的次数
long long ans = 0;
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
ans += cnt[k - x]; // 查 k-x 之前出现过几次，累加
cnt[x]++; // 再把当前数计入
}
cout << ans << "\n";
return 0;
}要点：① 核心套路——先查再加：遍历到 x 时，先看 k-x 之前出现过几次（这些都能和当前 x 配对），累加到答案，然后才把 x 记入 map。顺序不能反，否则会把自己和自己配对。② 这样一遍 O(n log n) 解决，避免了 O(n²) 双重循环（接 0.7）。③ 这里用 cnt[k-x] 查询是安全的（即使 k-x 不存在，map 会返回 0），但要注意这会创建键——数据量极大时可改用 cnt.count(k-x) ? cnt[k-x] : 0。
这 6 题的考点回顾：
- map 计数 + 自动有序输出
- pair + 双关键字 sort
- lower_bound + 验证值相等
- set 去重 vs vector+unique
- priority_queue 小根堆（合并果子模板）
- map 查存在（两数之和 O(n) 套路）
其中第 5 题（合并果子）和第 6 题（两数之和）是最经典的、后面会反复出现的模型，强烈建议彻底吃透。
把你的代码贴给我，我帮你看 STL 用得对不对、有没有隐藏的坑（特别是第 3 题的越界验证、第 5 题的 long long、第 6 题的先查后加顺序）。或者你都过了，我们就推进 1.2 排序与二分，重点讲「二分答案」——这是铜牌阶段一个能解决很多看似很难的题的强力技巧。
1.2 排序与二分
进入 1.2 排序与二分。排序你已经会用 sort 了，这节快速补充几个实战要点，然后重点讲「二分」——尤其是「二分答案」，这是铜牌阶段一个能把「看起来很难」的题瞬间变简单的强力武器，性价比极高，必须吃透。
一、排序的实战补充（快速过）
sort 的基本用法 1.1 讲过了，这里补几个实战常识：
① sort 的复杂度是 O(n log n)，n = 10⁶ 也就 2×10⁷ 量级，很快，放心用。
② 结构体排序的两种写法——除了 1.1 的 lambda，也可以重载运算符：
struct Node {
int x, y;
bool operator<(const Node& o) const { // 定义「<」，sort 就知道怎么排
if (x != o.x) return x < o.x;
return y < o.y;
}
};
sort(a.begin(), a.end()); // 直接排，用上面定义的规则两种写法选一个用顺手的。lambda 灵活（不同地方可以用不同规则），重载运算符一劳永逸（写一次到处能用，set/map 也能直接用这个结构体）。
③ 稳定排序 stable_sort：当你需要「值相等的元素保持原来的相对顺序」时用它，普通 sort 不保证这点。铜牌阶段很少用到，知道有就行。
④ 排序是很多算法的预处理步骤：贪心几乎都要先排序，二分查找前必须排序，离散化要排序去重。「先排序」是一种重要的解题直觉——很多题排完序就豁然开朗。
二、二分查找：在有序数据里快速定位
二分的核心思想：每次砍掉一半的搜索范围，O(log n) 就能在海量数据里定位。前提是数据有序/有单调性。
最朴素的手写二分（虽然 1.1 的 lower_bound 更方便，但你要理解原理，因为二分答案要手写）：
// 在有序数组 a[0..n-1] 中查找 x，返回下标，找不到返回 -1
int l = 0, r = n - 1;
while (l <= r) {
int mid = l + (r - l) / 2; // 防溢出写法，别写 (l+r)/2
if (a[mid] == x) return mid;
else if (a[mid] < x) l = mid + 1; // x 在右half
else r = mid - 1; // x 在左half
}
return -1;两个细节：
mid = l + (r - l) / 2而不是(l + r) / 2——当 l、r 都很大时l+r可能溢出，这个写法防溢出（接 0.2）。- 简单查找直接用
lower_bound就行（1.1 讲过），手写二分主要是为了下面的「二分答案」。
三、二分答案：本节的核心王牌（重点中的重点）
这是一个思维方式的转变，掌握后你会发现很多「不知道怎么直接求」的题，突然就有解法了。
核心思想
有些题，直接求答案很难，但「验证某个答案对不对」很容易。这时就可以——二分枚举答案，对每个猜测的答案做验证，逐步逼近正确答案。
把「求最优解」问题，转化成「判断某个值是否可行」的问题。
什么样的题能用二分答案？（识别特征）
满足这两个条件就能用：
- 答案具有单调性：如果答案 x 可行，那么所有比 x 更宽松的值也可行（或都不可行）。换句话说，存在一个分界点，分界点一边全可行、另一边全不可行。
- 给定一个答案，能快速验证它可行不可行（通常 O(n) 或 O(n log n) 写个 check 函数）。
典型信号：题目问「最大的最小值」「最小的最大值」「最多/最少能怎样」，并且答案在一个范围内单调——看到这种描述，第一反应就是二分答案。
二分答案的模板（背下来）
bool check(int x) {
// 判断「答案为 x」时是否可行，返回 true/false
// 这是核心，每道题不一样，但通常是个 O(n) 的扫描
}
int l = 最小可能答案, r = 最大可能答案;
while (l < r) {
int mid = l + (r - l) / 2;
if (check(mid)) r = mid; // mid 可行，答案可能是 mid 或更小，往左缩
else l = mid + 1; // mid 不可行，答案必须更大，往右缩
}
// 循环结束，l 就是答案
cout << l << "\n";这个模板求的是「满足条件的最小值」。如果求「满足条件的最大值」，把 check 逻辑和缩范围方向调一下（下面例题会演示）。先把这个模板抄到你的模板库，做几道题就熟了。
例题精讲 1：跳石头（最大化最小值）
题意：一条河上有一排石头，你要移走最多 m 块石头，使得剩下相邻石头之间的最小距离尽可能大。求这个「最大化的最小距离」。
为什么是二分答案：问「最小距离的最大值」——典型的「最大化最小值」信号。而且距离有单调性：如果「最小距离 ≥ 5」能做到（移走的石头数 ≤ m），那「最小距离 ≥ 3」肯定也能做到（更容易）。
思路：
- 二分这个「最小距离」d。
check(d)：贪心地走一遍，如果相邻石头距离 < d 就移走后面那块，统计要移走几块。移走数 ≤ m 就说明 d 可行。
int n, m; // n 块石头(不含起终点)，最多移 m 块
int L; // 河长
int stone[N]; // 石头位置（含起点0和终点L，已排序）
bool check(int d) { // 最小距离能否达到 d
int cnt = 0; // 移走的石头数
int last = 0; // 上一块保留的石头位置（从起点开始）
for (int i = 1; i <= n + 1; i++) { // 遍历到终点
if (stone[i] - last < d) cnt++; // 距离不够，移走这块
else last = stone[i]; // 距离够，保留，更新 last
}
return cnt <= m; // 移走数不超过 m 就可行
}
int main() {
// ... 读入，stone[0]=0, stone[n+1]=L ...
int l = 1, r = L; // 距离范围 [1, 河长]
while (l < r) {
int mid = l + (r - l + 1) / 2; // 注意：求最大值，mid 上取整
if (check(mid)) l = mid; // 可行，往大了试
else r = mid - 1; // 不可行，缩小
}
cout << l << "\n";
}注意这里是「求最大值」的变体：
mid = l + (r - l + 1) / 2要上取整（+1），否则l = mid时可能死循环。- check 可行时
l = mid（往大了找），不可行r = mid - 1。
求最小值 vs 求最大值的模板区别，这是二分答案最容易搞混的地方，给你对照清楚：
| | 求满足条件的最小值 | 求满足条件的最大值 |
|---|---|---|
| mid 取法 |l + (r-l)/2（下取整） |l + (r-l+1)/2（上取整）|
| check 为真 |r = mid|l = mid|
| check 为假 |l = mid + 1|r = mid - 1|记忆法：
l = mid出现时，mid 必须上取整（+1），否则死循环。这是唯一要记的坑。
例题精讲 2：分段问题（最小化最大值）
题意：把一个数组 a[1..n] 分成连续的 m 段，使得「所有段中和最大的那一段」尽可能小。求这个最小化的最大段和。（经典题：「数列分段」「把书分给抄写员」）
为什么是二分答案：问「最大段和的最小值」——「最小化最大值」信号。单调性：如果「每段和 ≤ 100」能分成 ≤ m 段，那「每段和 ≤ 200」肯定也能（更宽松，段数更少）。
思路：
- 二分「每段和的上限」x。
check(x)：贪心地从左往右尽量往一段里塞，超过 x 就开新段，统计需要几段。段数 ≤ m 就说明 x 可行。
int n, m;
int a[N];
bool check(int x) { // 每段和不超过 x，能否分成 ≤ m 段
int cnt = 1; // 当前段数
int sum = 0; // 当前段的和
for (int i = 1; i <= n; i++) {
if (sum + a[i] > x) { // 加上 a[i] 超了，开新段
cnt++;
sum = a[i];
} else {
sum += a[i];
}
}
return cnt <= m;
}
int main() {
// ... 读入 ...
int l = *max_element(a + 1, a + n + 1); // 下界：最大的单个元素（每段至少装得下它）
int r = accumulate(a + 1, a + n + 1, 0); // 上界：全部加起来（只分一段）
while (l < r) {
int mid = l + (r - l) / 2; // 求最小值，下取整
if (check(mid)) r = mid; // 可行，往小了试
else l = mid + 1; // 不可行，增大
}
cout << l << "\n";
}这里是「求最小值」的标准模板：mid 下取整，check 真则 r = mid。
注意二分的上下界设定（一个常见易错点）：
- 下界
l= 最大的单个元素（因为再怎么分，那个最大元素总得单独在某段里，段和至少是它）。 - 上界
r= 所有元素之和（只分一段的情况）。 max_element和accumulate是 STL 自带的求最大值/求和函数，很方便。
四、二分答案的解题步骤总结（套路化）
遇到疑似二分答案的题，按这个流程走：
- 识别：是不是「最大化最小值 / 最小化最大值 / 最多最少」类问题？答案有没有单调性？
- 确定二分对象：要二分的「答案」是什么（距离？段和？时间？数量？）。
- 确定上下界：l 和 r 的合理范围（往往 l 是理论最小、r 是理论最大，给宽点没关系，反正 log 很快）。
- 写 check 函数：给定一个答案 x，怎么判断它可行——这是核心难点，通常是个贪心扫描。
- 套模板：根据求最大还是求最小，选对应的 mid 取法和缩范围方向。
二分答案的威力：它把「直接求最优解」（往往很难）转化成「验证一个解」（往往简单）。check 函数通常是 O(n)，外层二分 O(log(范围))，总复杂度 O(n log(范围))，能处理很大的数据。很多铜牌区的题，正解就是二分答案，识别出来就赢了一半。
五、本节速记卡
- 排序：
sort+ lambda / 重载<；「先排序」是重要解题直觉。 - 二分查找：有序数据里 O(log n) 定位；简单查找用
lower_bound，原理要会手写。 - 二分答案（核心）：「直接求答案难、验证答案易」+「答案单调」→ 二分答案。
- 识别信号：「最大化最小值」「最小化最大值」「最多/最少能否」。
- 模板：写
check(x)验证函数 + 二分框架。求最大值记得 mid 上取整、l = mid。 - 复杂度：O(n log(值域))，能处理大数据。
二分答案是你学到现在第一个「有点威力」的算法技巧——前面都是工程和工具，这个是真正能解题的思想武器。它的精髓是转化问题：不会直接求，那就「猜 + 验证」。这种思想在竞赛里反复出现，务必通过做题彻底内化。
要不要我出几道二分答案的题（从「跳石头」「数列分段」这类模板题，到稍微需要自己想 check 函数的变体）让你练手？二分答案这东西看懂容易、自己写 check 容易卡，强烈建议立刻做题巩固。或者直接往下讲 1.3 前缀和与差分（另一个超高频、超实用的基础技巧）？
配套练习题
好，给你 5 道二分答案的题，难度阶梯式上升：前两道是模板题（直接套），中间两道要自己想 check 函数，最后一道是稍微换皮的变体。
二分答案的难点从来不是二分框架，而是①能不能识别出"这题要用二分答案" ②check 函数怎么写。这组题就是专门练这两点。
老规矩：先自己写，重点是想清楚 check 怎么写，再展开对照。
第 1 题：跳石头（最大化最小值 —— 模板裸题）
题意：起点 0、终点 L，中间有 n 块石头，位置已知。最多移走 m 块石头（起点终点不能移），使剩下相邻石头（含起终点）的最小间距最大。求这个最大化的最小间距。
输入样例
25 5 2
2 11 14 17 21
输出样例
4（L=25，5块石头，移走2块。移走11和14后，间距序列变成 2→17→21→25，最小间距是4）
考点：最大化最小值的标准模板。check(d)：贪心走一遍，间距不够 d 就移走，统计移走数 ≤ m 是否成立。
AC第 1 题 参考（跳石头）▸
#include <bits/stdc++.h>
using namespace std;
int L, n, m;
vector<int> stone; // 含起点0和终点L
bool check(int d) { // 最小间距能否 ≥ d
int cnt = 0, last = 0; // 移走数，上一块保留的位置
for (int i = 1; i < stone.size(); i++) {
if (stone[i] - last < d) cnt++; // 间距不够，移走
else last = stone[i]; // 够，保留
}
return cnt <= m;
}
int main() {
cin >> L >> n >> m;
stone.push_back(0);
for (int i = 0; i < n; i++) {
int x; cin >> x;
stone.push_back(x);
}
stone.push_back(L);
// 题目保证有序，若不保证要 sort
int l = 1, r = L;
while (l < r) {
int mid = l + (r - l + 1) / 2; // 最大值，上取整
if (check(mid)) l = mid;
else r = mid - 1;
}
cout << l << "\n";
return 0;
}要点：最大化最小值模板。mid 上取整 + check 真则 l = mid。
第 2 题：数列分段（最小化最大值 —— 模板裸题）
题意：把 n 个正整数的序列分成连续的 m 段，使和最大的那一段的和最小。求这个值。
输入样例
5 3
4 2 4 5 1
输出样例
6（分成 [4,2] [4] [5,1]，三段和分别是 6、4、6，最大段和为6，这是最优）
考点：最小化最大值的标准模板。check(x)：贪心分段，超过 x 就开新段，统计段数 ≤ m 是否成立。下界是最大单元素，上界是总和。
AC第 2 题 参考（数列分段）▸
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> a;
bool check(int x) { // 每段和 ≤ x，能否分成 ≤ m 段
int cnt = 1, sum = 0;
for (int i = 0; i < n; i++) {
if (sum + a[i] > x) { cnt++; sum = a[i]; }
else sum += a[i];
}
return cnt <= m;
}
int main() {
cin >> n >> m;
a.resize(n);
int l = 0, r = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
l = max(l, a[i]); // 下界：最大单元素
r += a[i]; // 上界：总和
}
while (l < r) {
int mid = l + (r - l) / 2; // 最小值，下取整
if (check(mid)) r = mid;
else l = mid + 1;
}
cout << l << "\n";
return 0;
}要点：最小化最大值模板。下界必须是最大单元素（不是1），否则会算出比单个元素还小的段和，逻辑错误。
第 3 题：木材加工（自己想 check —— 略微变形）
题意：有 n 根木头，长度分别为 a[i]。你要把它们切成至少 k 段相同长度的小段（每根可以切成若干段，剩余不足的部分丢弃）。求每段的最大长度。如果切不出 k 段，输出 0。
输入样例
3 7
232 124 456
输出样例
114（每段长114时：232能切2段，124能切1段，456能切4段，共7段，正好≥7。再长一点就不够7段了）
考点：二分"每段长度"len。check(len) 要自己想：每根木头 a[i] 能切出 a[i] / len 段（整除），把所有木头能切的段数加起来，看是否 ≥ k。这是「最大化」类型（段越长越难凑够 k 段）。
提示：注意 len = 0 的处理（不能除以 0），二分下界从 1 开始。
AC第 3 题 参考（木材加工）▸
#include <bits/stdc++.h>
using namespace std;
int n;
long long k;
vector<int> a;
bool check(int len) { // 每段长 len，能否切出 ≥ k 段
long long cnt = 0;
for (int i = 0; i < n; i++) {
cnt += a[i] / len; // 这根木头能切出几段
}
return cnt >= k;
}
int main() {
cin >> n >> k;
a.resize(n);
int r = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
r = max(r, a[i]); // 上界：最长的木头
}
int l = 1; // 下界从 1（不能为 0，要做除数）
// 特判：如果按长度1都切不出k段，输出0
if (!check(1)) { cout << 0 << "\n"; return 0; }
while (l < r) {
int mid = l + (r - l + 1) / 2; // 最大值，上取整
if (check(mid)) l = mid; // 段数够，往长了试
else r = mid - 1; // 段数不够，缩短
}
cout << l << "\n";
return 0;
}要点：① check 用整除 a[i]/len 算每根能切几段；② 下界从1（防除0）；③ 这是「最大化」（长度越大越难凑够段数），所以 check 真往大走；④ 切不出k段时特判输出0。④ 段数累加用 long long（木头多时可能超int）。
第 4 题：晋升者（自己想 check —— 计数型）
题意：n 个人排队，每人有一个能力值 a[i]。如果设定一个「晋升分数线」x，那么能力值 ≥ x 的人全部晋升。现在希望晋升的人数恰好 ≤ k 个（人太多了要卡一卡）。求最低能设多少的分数线 x，使得晋升人数 ≤ k。（x 可以是任意正整数）
输入样例
5 2
1 5 3 8 6
输出样例
6（分数线设6时，≥6的有 8和6 共2人，正好≤2；设5的话 5、8、6 三人就超了。所以最低设6）
考点：二分"分数线"x。check(x)：统计有多少人 ≥ x，判断是否 ≤ k。单调性思考：x 越高，晋升的人越少。我们要的是「人数 ≤ k」成立的最小 x——这是「最小化」型，check 真往左缩。
提示：先想清楚单调方向——x 增大时晋升人数是减少的，所以"人数≤k"这个条件随 x 增大从"假"变"真"，求第一个为真的 x（最小值模板）。
AC第 4 题 参考（晋升者）▸
#include <bits/stdc++.h>
using namespace std;
int n, k;
vector<int> a;
bool check(int x) { // 分数线 x，晋升人数是否 ≤ k
int cnt = 0;
for (int i = 0; i < n; i++)
if (a[i] >= x) cnt++; // 能力 ≥ x 的晋升
return cnt <= k;
}
int main() {
cin >> n >> k;
a.resize(n);
int r = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
r = max(r, a[i]);
}
int l = 1;
// x 越大晋升越少，"人数≤k"随 x 增大从假变真，求最小的真
while (l < r) {
int mid = l + (r - l) / 2; // 最小值，下取整
if (check(mid)) r = mid; // 人数已≤k，试试更低的线
else l = mid + 1; // 人还太多，提高线
}
cout << l << "\n";
return 0;
}要点：关键在想清单调方向——x 增大→晋升人数减少→"人数≤k"从假变真。要求最小的满足条件的 x，用最小值模板（下取整 + check真往左）。这题的难点纯粹是理清单调性，框架是标准的。
第 5 题：奶牛晒太阳（经典换皮 —— 最大化最小值变体）
题意：n 头奶牛要住进一排牛棚，牛棚有 m 个，位置在数轴上为 x[i]（m ≥ n）。奶牛们脾气暴躁，要让任意两头奶牛之间的最小距离尽可能大。求这个最大化的最小距离。（每个牛棚最多住一头牛）
输入样例
5 3
1 2 8 4 9
输出样例
3（5个牛棚排序后 1 2 4 8 9，放3头牛在 1、4、9（或1、4、8），最小间距为3最优）
考点：经典的「最大化最小值」，但 check 不是统计移走数，而是贪心地放牛。check(d)：排序后，从第一个位置放第一头牛，之后每隔 ≥ d 放一头，看能不能放下 ≥ n 头牛。这题和跳石头是"同一个模子的两道题"，体会一下二分答案的通用性。
提示：位置要先排序！（输入是乱的）
参考答案，写完再看：
AC第 5 题 参考（奶牛晒太阳/牛棚分配）▸
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> x;
bool check(int d) { // 任意两牛间距 ≥ d，能否放下 n 头
int cnt = 1, last = x[0]; // 第一头放在第一个位置
for (int i = 1; i < m; i++) {
if (x[i] - last >= d) { // 离上一头 ≥ d，放一头
cnt++;
last = x[i];
}
}
return cnt >= n; // 能放下 ≥ n 头就可行
}
int main() {
cin >> n >> m;
x.resize(m);
for (int i = 0; i < m; i++) cin >> x[i];
sort(x.begin(), x.end()); // 关键：先排序！
int l = 1, r = x[m-1] - x[0]; // 间距范围
while (l < r) {
int mid = l + (r - l + 1) / 2; // 最大值，上取整
if (check(mid)) l = mid;
else r = mid - 1;
}
cout << l << "\n";
return 0;
}要点：① 必须先排序（输入乱序）；② check 贪心放牛——第一头放最左，之后每隔 ≥ d 放一头，能放 ≥ n 头则 d 可行；③ 和跳石头几乎一模一样的模板，区别只是 check 里"统计能放几头"vs"统计要移几块"。体会模板的通用性。
考点回顾与难度梯度：
- 跳石头——最大化最小值，纯模板
- 数列分段——最小化最大值，纯模板（注意下界）
- 木材加工——自己想 check（整除算段数），最大化型
- 晋升者——自己想 check（计数），难在理清单调方向
- 牛棚分配——换皮的最大化最小值，练模板迁移
最该掌握的认知：第1、3、5 题都是「最大化」（上取整 + l=mid），第2、4 题都是「最小化」（下取整 + r=mid）。做完这5题，你应该能感觉到——二分框架是死的，活的是 check 函数和单调方向的判断。
把代码贴给我，我重点帮你看：check 函数对不对、上下界设得合不合理、求最大/最小用的模板对不对（尤其第3题的特判、第4题的单调方向、第5题的排序）。或者你都过了，我们推进 1.3 前缀和与差分——又一个高频到爆、几乎每场都能用上的实用技巧。
1.3 前缀和与差分
进入 1.3 前缀和与差分。这俩是一对孪生兄弟，思想简单但用途极广，几乎每场比赛都能用上。它们能把「区间求和」「区间修改」这类操作从 O(n) 降到 O(1)，是性价比极高的基础工具。
先一句话抓住本质：
前缀和解决「反复查询区间和」——预处理一次，每次查询 O(1)。
差分解决「反复对区间整体加减」——修改时 O(1)，最后还原一次。
它俩互为逆运算：前缀和的「差」是原数组，差分的「和」是原数组。
一、前缀和（一维）—— 区间求和神器
解决什么问题
给一个数组，多次询问「第 l 个到第 r 个元素的和是多少」。
- 暴力做法：每次询问都从 l 加到 r，单次 O(n)，q 次询问 O(nq)，数据大就 TLE。
- 前缀和做法：预处理一个前缀和数组，每次询问 O(1)。
核心定义与公式
定义 s[i] = 前 i 个元素的和 = a[1] + a[2] + ... + a[i]。
递推求前缀和：
s[i] = s[i-1] + a[i]; // 前 i 个的和 = 前 i-1 个的和 + 第 i 个查询区间 [l, r] 的和（核心公式，背死）：
区间和 = s[r] - s[l-1];为什么：s[r] 是前 r 个的和，s[l-1] 是前 l-1 个的和，相减就剩下第 l 到第 r 个。画个图秒懂：
s[r] = a[1] + a[2] + ... + a[l-1] + a[l] + ... + a[r]
s[l-1] = a[1] + a[2] + ... + a[l-1]
相减 = a[l] + ... + a[r] ← 正是 [l,r] 的和完整代码模板
const int N = 1e5 + 5;
long long s[N]; // 前缀和数组，开 long long 防溢出！
int main() {
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) { // 强烈建议下标从 1 开始
int a;
cin >> a;
s[i] = s[i-1] + a; // 边读边求前缀和
}
while (q--) {
int l, r;
cin >> l >> r;
cout << s[r] - s[l-1] << "\n"; // O(1) 查询
}
return 0;
}教教练衔接coach关键细节：
- 下标从 1 开始！这样s[l-1]在 l=1 时变成s[0]=0，不会越界，公式统一。这是前缀和强烈建议从 1 开始的原因。
- 前缀和数组开long long（接 0.2）：n 个数累加，即使每个数不大，总和也容易超 int。这是前缀和最常见的 WA 点。
二、二维前缀和 —— 子矩阵求和
解决什么问题
给一个矩阵，多次询问「以 (x1,y1) 为左上角、(x2,y2) 为右下角的子矩阵元素和」。
核心公式（容斥原理）
定义 s[i][j] = 从 (1,1) 到 (i,j) 这个矩形内所有元素的和。
求二维前缀和（容斥，背模板）：
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];查询子矩阵 (x1,y1)~(x2,y2) 的和：
和 = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];这两个公式都是容斥原理（加加减减避免重复）。理解靠画图，记忆靠模板：
求 s[i][j]：上面的块 + 左边的块 - 重复减的左上块 + 自己
查询：大矩形 - 上条 - 左条 + 被减两次的左上角补回来模板代码
const int N = 1005;
long long s[N][N];
int main() {
int n, m, q;
cin >> n >> m >> q;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
int a; cin >> a;
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a;
}
while (q--) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1] << "\n";
}
return 0;
}二维前缀和的两个公式记不住没关系，存进模板库，用的时候抄。理解「容斥」的思想即可：算重复的部分要减掉，减重复了再加回来。
三、差分（一维）—— 区间修改神器
差分是前缀和的逆操作，解决相反的问题。
解决什么问题
多次操作「把第 l 到第 r 个元素都加上 x」，所有操作做完后，问最终数组长什么样。
- 暴力做法：每次操作都从 l 到 r 挨个加，单次 O(n)，q 次 O(nq)，慢。
- 差分做法：每次修改只动两个位置，O(1)；所有修改做完，求一次前缀和还原，总 O(n+q)。
核心思想
定义差分数组 d，使得它的前缀和就是原数组。即 d[i] = a[i] - a[i-1]（相邻两项的差）。
关键魔法：要给区间 [l, r] 整体加 x，只需：
d[l] += x; // 从 l 开始，后面都 +x
d[r+1] -= x; // 到 r+1 处，把多加的 x 减掉为什么有效：差分数组求前缀和会还原成原数组。在 d[l] 加 x，会让还原后从 l 开始的所有位置都 +x；在 d[r+1] 减 x，会让从 r+1 开始的所有位置都 -x。两者叠加，净效果就是 [l,r] 这一段 +x，其余不变。
位置: 1 2 3 4 5 6
d[l]+=x: +x → → → → (从3开始全+x)
d[r+1]-=x: -x → → (从5开始全-x)
净效果: +x +x (只有3、4被+x，正是[3,4])模板代码
const int N = 1e5 + 5;
long long d[N]; // 差分数组
int main() {
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) {
int a; cin >> a;
d[i] = a - (i > 1 ? 上一个a : 0); // 也可以先读入原数组再求差分
}
// 更简单：把初始数组也看成 q 次"单点加"，初始 d 全 0，逐个加
// 这里演示标准流程：
while (q--) {
int l, r, x;
cin >> l >> r >> x;
d[l] += x; // 区间修改 O(1)
d[r+1] -= x;
}
// 所有修改完成，求前缀和还原出最终数组
for (int i = 1; i <= n; i++) {
d[i] += d[i-1]; // d 求前缀和 = 最终的 a
cout << d[i] << " ";
}
return 0;
}实战中更常用的简洁写法——把「读入初始值」也当成差分操作，初始数组全 0，每个位置 a[i] 相当于对区间 [i,i] 加 a[i]：
const int N = 1e5 + 5;
long long d[N];
int main() {
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) {
int a; cin >> a;
d[i] += a; d[i+1] -= a; // 把初始值看成对 [i,i] 加 a
}
while (q--) {
int l, r, x;
cin >> l >> r >> x;
d[l] += x; d[r+1] -= x; // 区间加
}
for (int i = 1; i <= n; i++) {
d[i] += d[i-1]; // 前缀和还原
cout << d[i] << " ";
}
}差分的核心记忆：「区间 [l,r] 加 x →
d[l]+=x, d[r+1]-=x，最后求前缀和还原」。这三步是固定套路。
注意d[r+1]可能用到d[n+1]，所以数组要多开一格（接 0.3 数组多开的习惯）。
四、前缀和 vs 差分 —— 一张表理清
| 前缀和 | 差分 | |
|---|---|---|
| 解决问题 | 多次查询区间和 | 多次修改区间值 |
| 核心操作 | s[i]=s[i-1]+a[i] | d[l]+=x, d[r+1]-=x |
| 查询/还原 | s[r]-s[l-1] | 最后求一遍前缀和 |
| 修改后能再改吗 | 不能（数组固定才能用） | 不能（要先全改完再还原） |
| 关系 | 互为逆运算 | 差分的前缀和 = 原数组 |
关键区别：
- 前缀和适用于「数组不变，反复查询」。如果数组中途要改，前缀和就失效了（要重算）。
- 差分适用于「反复区间修改，最后查一次结果」。修改过程中不能查中间状态。
- 如果既要改又要查（边改边查），那就超出前缀和/差分的能力了，需要树状数组或线段树（第七部分）。
五、典型应用场景（识别信号）
看到这些描述，想到前缀和/差分：
前缀和：
- 「多次询问区间和 / 子矩阵和」→ 一维/二维前缀和。
- 「求满足某条件的连续子数组」→ 常用前缀和转化（比如「和为 k 的子数组个数」，前缀和 + map，接 1.1 第6题的思想）。
- 「统计某区间内满足条件的元素个数」→ 前缀和记录个数。
差分：
- 「给区间整体加值，多次操作」→ 一维差分。
- 「区间染色 / 区间计数 / 多个区间叠加」→ 差分。
- 经典题「会议室/航班预订」：多个区间各自 +1，问每个位置被覆盖几次 → 差分裸题。
- 「最大的同时段重叠数」（比如最多多少个活动时间重叠）→ 差分 + 求前缀和找最大值。
六、本节速记卡
- 前缀和（查询区间和）：
s[i]=s[i-1]+a[i]，查询s[r]-s[l-1]。下标从1、开 long long。 - 二维前缀和：求和与查询各一个容斥公式，存模板抄。
- 差分（区间修改）：
d[l]+=x, d[r+1]-=x，最后求前缀和还原。数组多开一格。 - 互逆关系：前缀和 ↔ 差分。
- 识别：多次查区间和→前缀和；多次区间加→差分；既改又查→树状数组/线段树。
这俩工具的精髓是「预处理 / 延迟处理」的思想：前缀和提前算好，把每次查询摊薄到 O(1)；差分延迟还原，把每次修改摊薄到 O(1)。用空间和一次性预处理，换取每次操作的高效——这种思想在竞赛里反复出现。
前缀和、差分都是「看懂很简单，但要做题才能形成条件反射」的典型。尤其是识别「这题该用前缀和/差分」比写代码更重要。
要不要我出一组前缀和 + 差分的题（包括一维前缀和、二维前缀和、差分区间加、以及"前缀和+map求子数组"这种经典组合）让你练手？还是直接往下讲 1.4 双指针 / 尺取法？
配套练习题
好，给你 6 道题，覆盖前缀和/差分的核心场景：一维前缀和、二维前缀和、差分区间加、差分经典应用、以及"前缀和 + map"这个高频组合。难度阶梯上升，最后两道需要点转化思维。
老规矩：先自己写，重点想清楚"这题该用前缀和还是差分"，再展开对照。
第 1 题：区间求和（一维前缀和 —— 裸题）
题意：给 n 个整数，q 次询问，每次问区间 [l, r] 的元素和。
输入样例
5 3
1 2 3 4 5
1 3
2 5
1 5
输出样例
6
14
15考点：一维前缀和模板。s[i]=s[i-1]+a[i]，查询 s[r]-s[l-1]。记得开 long long、下标从1。
AC第 1 题 参考（一维前缀和）▸
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
long long s[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) {
int a; cin >> a;
s[i] = s[i-1] + a;
}
while (q--) {
int l, r;
cin >> l >> r;
cout << s[r] - s[l-1] << "\n";
}
return 0;
}要点：下标从1，s[0]=0 自动处理 l=1 的边界。开 long long。
第 2 题：子矩阵求和（二维前缀和 —— 裸题）
题意：给一个 n×m 的矩阵，q 次询问，每次给左上角 (x1,y1) 和右下角 (x2,y2)，求该子矩阵的元素和。
输入样例
3 3 2
1 2 3
4 5 6
7 8 9
1 1 2 2
2 2 3 3
输出样例
12
28（第一个子矩阵是左上2×2：1+2+4+5=12；第二个是右下2×2：5+6+8+9=28）
考点：二维前缀和。两个容斥公式（求和 + 查询）。
AC第 2 题 参考（二维前缀和）▸
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
long long s[N][N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, q;
cin >> n >> m >> q;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
int a; cin >> a;
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a;
}
while (q--) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1] << "\n";
}
return 0;
}要点：求和与查询两个容斥公式。理解"加重复的减掉、减重复的加回"。
第 3 题：区间加法（差分 —— 裸题）
题意：一个长度为 n 的数组，初始全为 0。进行 q 次操作，每次把区间 [l, r] 的所有元素加上 x。输出所有操作后的最终数组。
输入样例
5 3
1 3 2
2 4 1
1 5 3（操作1：[1,3]+2；操作2：[2,4]+1；操作3：[1,5]+3）
输出样例
5 6 6 4 3（位置1：2+3=5；位置2：2+1+3=6；位置3：2+1+3=6；位置4：1+3=4；位置5：3）
考点：差分模板。d[l]+=x, d[r+1]-=x，最后求前缀和还原。数组多开一格。
AC第 3 题 参考（差分）▸
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
long long d[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
while (q--) {
int l, r, x;
cin >> l >> r >> x;
d[l] += x;
d[r+1] -= x; // 注意 r+1 可能到 n+1，数组要够大
}
for (int i = 1; i <= n; i++) {
d[i] += d[i-1]; // 前缀和还原
cout << d[i] << " ";
}
cout << "\n";
return 0;
}要点：差分三步——d[l]+=x、d[r+1]-=x、最后求前缀和。d[r+1] 用到 n+1，数组多开。
第 4 题：航班预订（差分经典应用 —— 略微换皮）
题意：有 n 个航班（编号 1~n）。给你 q 条预订记录，每条是 [first, last, seats]，表示从航班 first 到航班 last，每个航班都预订了 seats 个座位。求每个航班最终被预订的总座位数。
输入样例
5 3
1 2 10
2 3 20
2 5 25
输出样例
10 55 45 25 25（航班1：10；航班2：10+20+25=55；航班3：20+25=45；航班4：25；航班5：25）
考点：这就是差分裸题换了个故事——每条记录是对区间 [first,last] 加 seats。识别出"区间整体加"就是差分。
AC第 4 题 参考（航班预订）▸
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
long long d[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
while (q--) {
int first, last, seats;
cin >> first >> last >> seats;
d[first] += seats; // 区间 [first,last] 加 seats
d[last+1] -= seats;
}
for (int i = 1; i <= n; i++) {
d[i] += d[i-1];
cout << d[i] << " ";
}
cout << "\n";
return 0;
}要点：和第3题代码几乎一样，只是变量名换成航班语境。识别"区间整体加"=差分是关键，故事是干扰。
第 5 题：最大重叠（差分求最值 —— 需要转化）
题意：有 n 个活动，每个活动有开始时间 s 和结束时间 e（活动在 [s, e] 时间段内进行，包含两端）。求任意时刻最多有多少个活动同时进行。时间范围 0~1000。
输入样例
3
1 5
2 6
4 8
输出样例
3（在时刻4或5，三个活动 [1,5]、[2,6]、[4,8] 都在进行，重叠数为3）
考点：每个活动对时间区间 [s,e] 做 +1（差分），最后求前缀和还原出"每个时刻的活动数"，取最大值。这是差分 + 求最值的经典组合。
提示：差分数组在每个时刻 [s,e] 加1，还原后扫一遍找最大值。
AC第 5 题 参考（最大重叠）▸
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int d[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int s, e;
cin >> s >> e;
d[s] += 1; // 区间 [s,e] 每个时刻 +1 个活动
d[e+1] -= 1;
}
int maxv = 0, cur = 0;
for (int t = 0; t <= 1000; t++) {
cur += d[t]; // 前缀和还原出时刻 t 的活动数
maxv = max(maxv, cur); // 求最大值
}
cout << maxv << "\n";
return 0;
}要点：差分记录每个时刻活动数变化，前缀和还原后边还原边取最大值。这是差分的进阶用法——不只是还原数组，而是在还原过程中统计信息。
第 6 题：和为 k 的子数组（前缀和 + map —— 经典组合，有难度）
题意：给 n 个整数（可能有负数）和一个目标值 k，求有多少个连续子数组的和恰好等于 k。
输入样例
5 5
1 2 3 -3 5
输出样例
3（满足的子数组：[2,3]、[1,2,3,-3]、[3,-3,5]，和都为5，共3个。注意因为有负数，不能用双指针，必须前缀和+map）
考点：把"子数组和"转成前缀和之差。子数组 [l,r] 的和 = s[r]-s[l-1]=k，即 s[l-1]=s[r]-k。遍历到 r 时，统计前面有多少个前缀和等于 s[r]-k，用 map 计数。这是 1.1 第6题"两数之和"思想的升级版（前缀和 + 哈希）。
提示：这题用双指针会错（有负数，没有单调性），必须前缀和+map。注意初始要 cnt[0]=1（表示空前缀，对应子数组从开头算起的情况）。
参考答案，写完再看：
AC第 6 题 参考（和为 k 的子数组）▸
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
long long k;
cin >> n >> k;
map<long long, int> cnt;
cnt[0] = 1; // 关键！空前缀和为0，出现1次
long long s = 0, ans = 0;
for (int i = 0; i < n; i++) {
long long a; cin >> a;
s += a; // 当前前缀和
ans += cnt[s - k]; // 找前面有多少个前缀和 = s-k
cnt[s]++; // 当前前缀和计入
}
cout << ans << "\n";
return 0;
}要点：① 核心转化——子数组 [l,r] 和为 k ⟺ s[r]-s[l-1]=k ⟺ s[l-1]=s[r]-k；② 先查后加（接1.1第6题），遍历到 r 先查 s[r]-k 出现几次，再把当前前缀和计入；③ cnt[0]=1 是易错点——表示"空前缀"，处理从数组开头开始的子数组（这种子数组的 l-1=0，对应前缀和0）；④ 有负数时只能用这个方法，双指针会错。
考点回顾与难度梯度：
- 一维前缀和——裸模板
- 二维前缀和——容斥公式
- 差分——裸模板
- 航班预订——差分换皮（识别"区间加"）
- 最大重叠——差分 + 求最值（进阶用法）
- 和为k的子数组——前缀和 + map（经典组合，有思维量）
最该吃透的两道：
- 第 4 题让你体会"识别"的重要性——同样是差分，套个故事就有人认不出来。会不会用前缀和/差分，关键在识别，不在写代码。
- 第 6 题是前缀和最经典的进阶应用，"前缀和之差 = 区间和"这个转化 + map 计数，在很多题里反复出现，务必吃透（注意那个
cnt[0]=1的坑）。
把代码贴给我，我重点帮你看：前缀和/差分识别对不对、long long 开了没、第5题的求最值、第6题的 cnt[0]=1 和先查后加顺序。或者你都过了，我们推进 1.4 双指针 / 尺取法——又一个高频实用技巧，和前缀和经常搭配出现。
1.4 双指针 / 尺取法
进入 1.4 双指针 / 尺取法。这是个思想极简但威力很大的技巧——用两个指针在数组上移动，把很多 O(n²) 的暴力优化成 O(n)。它和前缀和一样高频，而且经常和排序、前缀和搭配出现。
先抓核心：
双指针的本质是——用两个指针的协同移动，避免重复扫描。原本要双重循环枚举的东西，靠两个指针各扫一遍就解决，O(n²) → O(n)。
双指针主要有三种形式，我按使用频率讲。
一、形式一：对撞指针（左右往中间夹）
特征：一个指针 l 从左端、一个指针 r 从右端，相向移动，直到相遇。
经典应用：有序数组里找两数之和
题意：在已排序数组里，找两个数之和等于 target。
暴力：双重循环枚举所有对，O(n²)。 双指针：利用有序性，O(n)：
sort(a.begin(), a.end()); // 必须有序
int l = 0, r = n - 1;
while (l < r) {
int sum = a[l] + a[r];
if (sum == target) {
// 找到了
cout << a[l] << " " << a[r] << "\n";
break;
} else if (sum < target) {
l++; // 和太小，左指针右移（换个更大的数）
} else {
r--; // 和太大，右指针左移（换个更小的数）
}
}为什么对：数组有序时，sum 太小就增大左边（l++ 让 a[l] 变大），太大就减小右边（r-- 让 a[r] 变小）。每步要么 l++ 要么 r--，两指针总共走 n 步，O(n)。
对撞指针的核心：有序 + 根据当前结果决定移动哪个指针。判断回文串、三数之和、盛水容器等都是这个套路。
经典应用：判断回文串
bool isPalindrome(string s) {
int l = 0, r = s.size() - 1;
while (l < r) {
if (s[l] != s[r]) return false; // 对应位置不等，不是回文
l++;
r--;
}
return true;
}两端往中间比，简单直观。
二、形式二：快慢指针 / 同向指针（滑动窗口，最重要）
特征：两个指针同方向移动，r（右指针）不断扩张窗口，l（左指针）在条件不满足时收缩窗口。也叫尺取法或滑动窗口。这是双指针最重要、最高频的形式。
核心思想
维护一个「窗口」[l, r]，右指针 r 向右扩张纳入新元素，当窗口不满足条件时，左指针 l 向右收缩，直到窗口重新满足条件。整个过程 l 和 r 都只向右走，各走一遍，O(n)。
模板（背下来）
int l = 0;
for (int r = 0; r < n; r++) {
// 1. 把 a[r] 纳入窗口（更新窗口状态）
add(a[r]);
// 2. 当窗口不满足条件时，收缩左边界
while (窗口不满足条件) {
remove(a[l]); // 移除 a[l]
l++;
}
// 3. 此时 [l, r] 是满足条件的窗口，更新答案
ans = max(ans, r - l + 1); // 比如求最长窗口
}例题精讲 1：最长无重复字符子串
题意：找一个字符串中不含重复字符的最长子串的长度。
思路：滑动窗口，窗口内保证无重复字符。
- 右指针 r 不断纳入字符。
- 如果纳入
s[r]后窗口出现重复，左指针 l 右移，直到去掉那个重复字符。 - 用一个数组/map 记录窗口内每个字符的出现次数。
int lengthOfLongest(string s) {
int cnt[128] = {0}; // 记录窗口内每个字符出现次数
int l = 0, ans = 0;
for (int r = 0; r < s.size(); r++) {
cnt[s[r]]++; // 纳入 s[r]
while (cnt[s[r]] > 1) { // 出现重复（s[r] 计数 >1）
cnt[s[l]]--; // 移除左边字符
l++; // 收缩左边界
}
ans = max(ans, r - l + 1); // 更新最长长度
}
return ans;
}走一遍体会：abcabcbb
- r 扩到第二个
a时，窗口abca里 a 重复了，l 右移把第一个abc的 a 去掉，窗口变bca。 - 全程 l、r 各扫一遍，O(n)。
例题精讲 2：和 ≥ target 的最短连续子数组
题意：给一个正整数数组，找和 ≥ target 的最短连续子数组长度。
思路：滑动窗口。右指针扩张累加，一旦窗口和 ≥ target，就尝试收缩左边界求最短。
int minSubArray(vector<int>& a, int target) {
int l = 0, sum = 0, ans = INT_MAX;
for (int r = 0; r < a.size(); r++) {
sum += a[r]; // 纳入 a[r]
while (sum >= target) { // 窗口和够大，尝试缩短
ans = min(ans, r - l + 1); // 更新最短长度
sum -= a[l]; // 移除左边
l++; // 收缩
}
}
return ans == INT_MAX ? 0 : ans; // 没找到返回 0
}滑动窗口的适用前提（重要）：通常要求数组元素非负（或具有单调性），这样「扩张窗口和增大、收缩窗口和减小」才成立。如果有负数，滑动窗口就失效了（窗口和不单调），这时要用前缀和+map（接 1.3 第6题那个"和为k的子数组"，正是因为有负数才不能用双指针）。这是双指针最重要的适用边界，务必记住。
三、形式三：归并 / 双数组指针
特征：两个指针分别在两个数组上移动，常用于合并有序序列。
经典应用：合并两个有序数组
// a、b 都已排序，合并成有序的 c
int i = 0, j = 0;
vector<int> c;
while (i < a.size() && j < b.size()) {
if (a[i] <= b[j]) c.push_back(a[i++]); // 谁小放谁
else c.push_back(b[j++]);
}
// 把剩余的接上
while (i < a.size()) c.push_back(a[i++]);
while (j < b.size()) c.push_back(b[j++]);这就是归并排序的核心步骤。两个指针各扫一遍，O(n+m)。归并排序、求逆序对等都基于此。铜牌阶段了解即可。
四、双指针的识别信号（什么时候想到用）
看到这些特征，考虑双指针：
- 「连续子数组/子串」+「满足某条件的最长/最短/数量」 → 滑动窗口（最高频）。例：最长不重复子串、和为某值的子数组个数、最多包含k种元素的子串。
- 「有序数组」+「找两个数满足某关系」 → 对撞指针。例：两数之和、三数之和、盛最多水的容器。
- 「合并两个有序序列」 → 双数组指针。
- 判断回文 → 对撞指针。
关键判断：能不能用「移动指针」代替「重复枚举」。如果暴力是「固定一个端点，枚举另一个端点」的双重循环，且具有单调性（移动一个指针时，另一个指针不用回头），那就能用双指针优化。
五、双指针 vs 前缀和（容易混淆，理清）
这两个都能处理「连续子数组」问题，区别：
| 双指针/滑动窗口 | 前缀和(+map) | |
|---|---|---|
| 适用 | 元素非负、窗口有单调性 | 任意元素（含负数） |
| 求什么 | 最长/最短满足条件的窗口 | 和为定值的子数组个数等 |
| 复杂度 | O(n) | O(n) |
| 典型 | 最长不重复子串、最短和≥k子数组 | 和恰为k的子数组个数(有负数) |
口诀：全是正数求最长最短 → 双指针；有负数或求"和恰好等于"的个数 → 前缀和+map。 当然很多题两种都能做，灵活选择。
六、本节速记卡
- 对撞指针：左右往中间夹。有序数组找两数之和、回文判断。靠当前结果决定动哪个指针。
- 滑动窗口（最重要）：同向移动，r 扩张、l 收缩。模板：纳入 a[r] → while 不满足则收缩 l → 更新答案。
- 适用前提：元素非负 / 有单调性。有负数用前缀和+map，别用双指针。
- 双数组指针：归并有序序列。
- 识别：「连续子数组 + 最长/最短/计数」→ 滑动窗口；「有序 + 两数关系」→ 对撞指针。
双指针的精髓是「不回头」：通过分析问题的单调性，让指针只朝一个方向走，避免重复扫描。这是一种重要的优化思想——很多 O(n²) 暴力，找到单调性后用双指针就降到 O(n)。
和前面学的串一下：双指针、前缀和、二分这三个是处理「区间/子数组」问题的三大基础工具，经常组合使用。你现在已经把基础算法的核心工具集齐了一大半。
要不要我出一组双指针的题（对撞指针、滑动窗口求最长、滑动窗口求最短/计数，外加一道"双指针 vs 前缀和该用哪个"的判断题）练手？还是直接往下讲 1.5 贪心（你有基础，我会重点补充经典模型和"怎么证明/判断贪心对不对"）？
1.5 贪心
进入 1.5 贪心。你已经做过仓库选址、杂技牛这些经典贪心题了，所以这节我不从零讲概念，而是重点补三件你最需要的：①贪心的经典模型库（见过就秒杀）②怎么判断"这题能不能用贪心" ③贪心 vs DP 怎么选。这三点是贪心从"会做几道"到"稳定识别并解决"的关键。
先用一句话框定本质，再讲你真正缺的：
贪心 = 每一步都做"当前看起来最优"的选择，并期望最终全局最优。 它的难点从来不是写代码（贪心代码通常很短），而是 ①想到正确的贪心策略 ②确信这个策略是对的。
一、贪心最大的坑：策略对不对（先讲思维）
贪心最危险的地方在于——它经常"看起来对"，但实际是错的。新手最容易凭直觉选一个贪心策略就交，然后 WA。所以先建立判断方法。
怎么判断一个贪心策略对不对？
实战中三个层次（按可靠性）：
① 找反例（最实用）：想一个贪心策略后，主动构造小数据试图推翻它。如果你能找到一组数据让贪心得出非最优解，这个策略就是错的。找不到反例 ≠ 一定对，但能筛掉大量错误策略。
② 对拍验证（最可靠）：写个暴力解（枚举所有情况），和你的贪心对拍（接 0.6）。跑几千组随机小数据，全一致就大概率对。这是赛场上"不证而信"的核心手段——你没时间严格证明，但对拍能给你信心。
③ 严格证明（最难，赛场少用）：用交换论证、归纳法等证明。铜牌阶段不要求你会证，但要会用前两个方法验证。
关键心态：赛场上贪心策略想出来后，先找反例 + 对拍，别裸交。很多 WA 就是贪心策略错了还自信满满地交。这正是 0.8 讲的"猜结论 + 对拍验证"在贪心上的应用。
贪心的两个常见证明思路（了解，建立直觉）
虽然不要求严格证明，但理解这两个思路能帮你判断策略：
- 交换论证：假设最优解和贪心解不同，证明可以把最优解里的某一步"换成"贪心的选择而不变差，从而说明贪心也能达到最优。（排序类贪心常用）
- 决策包容性/无后效：证明当前的贪心选择不会让后面的选择变差，"现在拿最优不影响以后"。
二、贪心经典模型库（重点：见过就秒杀）
贪心题大多是经典模型的变体。把这些模型吃透，赛场上看到就能对号入座。
模型 1：排序后贪心（最常见的一类）
核心：先按某个关键字排序，然后顺序处理。"先排序"是贪心的头号直觉。
例：分发饼干——n 个孩子各有胃口 g[i]，m 块饼干各有大小 s[j]，一块饼干只能给一个孩子，饼干 ≥ 胃口才能满足。求最多满足几个孩子。
策略：两边都排序，用最小的饼干去满足最小胃口的孩子（双指针）。
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int child = 0, cookie = 0, cnt = 0;
while (child < n && cookie < m) {
if (s[cookie] >= g[child]) { // 这块饼干能满足这个孩子
cnt++;
child++;
}
cookie++; // 不管满不满足，这块饼干都用掉/跳过
}
cout << cnt << "\n";（贪心 + 双指针的结合，接 1.4）
模型 2：区间问题（极高频，必须掌握）
区间贪心有几个经典子模型，关键在于"按什么排序"：
子模型 2a：最多不重叠区间数（活动安排） 题意：n 个活动各有起止时间，同一时间只能进行一个，求最多能安排几个不重叠的活动。 策略：按结束时间从小到大排序，每次选结束最早且与已选不冲突的。
sort(a.begin(), a.end(), [](auto& x, auto& y) {
return x.second < y.second; // 按结束时间排序（关键！）
});
int cnt = 0, lastEnd = -INF;
for (auto& [start, end] : a) {
if (start >= lastEnd) { // 不冲突（开始时间 ≥ 上一个结束时间）
cnt++;
lastEnd = end; // 更新结束时间
}
}为什么按结束时间排：结束越早，留给后面的空间越多。这是区间贪心最经典的结论，务必记死。
子模型 2b：区间选点 / 用最少的点覆盖所有区间 按结束时间排序，每个区间没被覆盖就在它结束处放一个点。
子模型 2c：合并区间 按起始时间排序，依次合并有重叠的区间。
区间贪心的核心心法：90% 的区间贪心，要么按起点排、要么按终点排，选对排序方式题就解决了一大半。 求"最多不重叠/最少点覆盖"按终点排，求"合并"按起点排。
模型 3：哈夫曼 / 优先队列贪心
核心：每次取出最小的若干个合并，用小根堆实现。
例：合并果子（你已经做过，接 1.1 第5题）——每次合并最小的两堆，小根堆维护。这就是哈夫曼思想。
凡是"每次操作最小/最大的几个元素"的贪心，用 priority_queue（接 1.1）。
模型 4：相邻交换贪心（排序不等式）
核心：当排序规则不明显时，比较"相邻两个元素交换前后哪个更优"，推导出排序依据。你做过的"杂技牛"就是这类！
例：排队接水——n 个人接水各需 t[i] 时间，一个水龙头，求让所有人总等待时间最小的排队顺序。 策略：接水时间短的排前面（t[i] 升序）。
怎么想到的：考虑相邻两人 i、j，谁排前面总等待更小？如果 i 在前，j 要等 t[i]；如果 j 在前，i 要等 t[j]。所以时间小的在前更优。这种"通过相邻交换推导排序规则"是相邻交换贪心的精髓。
sort(t.begin(), t.end()); // 接水时间升序
long long wait = 0, total = 0;
for (int i = 0; i < n; i++) {
total += wait; // 第 i 个人的等待时间 = 前面所有人接水时间之和
wait += t[i]; // 累加接水时间
}
cout << total << "\n"; // total 是总等待时间杂技牛、国王游戏、排队接水都是这一类——通过"交换相邻两个元素哪个更优"推导出排序的比较函数。这是你已经接触过的模型，巩固一下：看到"求某种排列使总代价最小"，想相邻交换贪心。
模型 5：经典贪心结论（背一些）
有些贪心是固定结论，直接记：
- 找零钱/纸币：从大面额开始尽量多用（仅在特定币值体系下贪心才对，注意！）。
- 跳跃游戏：维护当前能到达的最远位置。
- 加油站问题：贪心找起点。
三、贪心 vs DP：怎么选（重要判断）
贪心和动态规划（下一大部分的重点）经常让人纠结。区别：
| 贪心 | DP | |
|---|---|---|
| 决策 | 每步选当前最优，不反悔 | 考虑所有可能，记录子问题最优 |
| 正确前提 | 局部最优能导出全局最优 | 有最优子结构 |
| 速度 | 快，通常 O(n) 或 O(n log n) | 慢些，常 O(n²) 或更高 |
| 风险 | 策略可能错（要验证） | 只要状态对就一定对 |
怎么判断该用哪个：
- 贪心能解决的，DP 一定能解决（但 DP 更慢）。贪心是 DP 的特例。
- 如果贪心策略找不到/不确定对，就用 DP（DP 更"无脑"，枚举所有情况，不容易错）。
- 典型信号：如果"当前的选择会影响后面、且需要权衡"，往往是 DP；如果"每步有个明显的最优选择且不影响后续"，往往是贪心。
- 经典例子对比：找零钱用贪心（特定币值）；但"凑出某金额的最少硬币数"（任意币值）必须用 DP，因为贪心会错（比如币值 1、3、4，凑 6，贪心选 4+1+1=3 枚，DP 选 3+3=2 枚才最优）。这个例子完美说明"贪心看起来对但会错"。
实战建议：拿不准贪心对不对、又能想出 DP 时，优先 DP 保稳（虽然慢点，但铜牌数据范围通常够）。贪心留给那些"策略明显正确"或"对拍验证过"的题。
四、贪心解题流程（套路化）
遇到疑似贪心的题：
- 观察问题：是不是"求最大/最小/最多/最少"的最优化问题？
- 想贪心策略：能不能找到一个"每步最优"的选择？常从排序入手（按什么排？）。
- 找反例验证：构造小数据试图推翻策略。能推翻就换策略。
- 对拍确认：写暴力对拍，跑几千组（接 0.6）。
- 不确定就转 DP：如果策略总是 WA 或想不出，改用 DP。
五、本节速记卡
- 贪心本质：每步选当前最优，难在"想对策略 + 确信策略对"。
- 验证策略：①找反例 ②对拍（赛场核心）③严格证明（少用）。别裸交贪心！
- 经典模型：
- 排序后贪心（最常见，先排序的直觉）
- 区间问题（最多不重叠按终点排，合并按起点排）
- 优先队列贪心（每次取最值，合并果子）
- 相邻交换贪心（杂技牛/排队接水，交换推导排序规则）
- 贪心 vs DP：策略明确用贪心（快），不确定用 DP（稳）。凑硬币是经典"贪心会错"案例。
贪心的精髓是"洞察"：找到那个让局部最优等于全局最优的"性质"。这需要大量见识经典模型——你做的题越多，越能一眼看出"这是活动安排模型""这是相邻交换模型"。所以贪心这块，刷模型题、积累套路比啥都重要。
你已经有杂技牛、仓库选址的基础，现在补齐了模型库和判断方法。要不要我出一组贪心题（覆盖区间贪心、相邻交换、优先队列贪心，以及一道"贪心会错、该用DP"的辨析题）让你练手 + 强化"识别模型"和"验证策略"的能力？还是直接进入 1.6 递归与分治？
配套练习题
好，给你 6 道贪心题，覆盖核心模型：区间贪心（按终点/起点排）、相邻交换、优先队列贪心，外加一道"贪心会错、暴露陷阱"的辨析题。这组题的重点是练 ①识别模型 ②想对排序依据 ③验证策略对不对。
老规矩：先自己写，重点想清楚"用什么贪心策略、按什么排序、这策略为什么对"，再展开对照。
第 1 题：活动安排（区间贪心 —— 按终点排，必会模型）
题意：有 n 个活动，每个有开始时间 s 和结束时间 e。同一时间只能参加一个活动（一个活动结束的瞬间可以紧接着开始下一个）。求最多能参加几个活动。
输入样例
4
1 3
2 5
4 7
6 8
输出样例
3（选 [1,3]、[4,7]... 不对，[4,7]和[6,8]冲突。最优：[1,3]、[4,7] 或者 [1,3]、[6,8]... 实际选 [1,3][4,7] 后6<7冲突。正解选[1,3][4,7]是2个？重新算：[1,3]→[4,7]→[6,8]中[6,8]与[4,7]冲突。应是[1,3][4,7]=2... 让我重选：按结束排序后 [1,3][2,5][4,7][6,8]，选[1,3]→下一个start≥3的是[4,7]→下一个start≥7的是无（[6,8]的6<7）。所以是2个。修正样例见下）
修正样例：
输入
4
1 3
3 5
5 7
2 4
输出
3（按结束时间排序：[1,3][2,4][3,5][5,7]，选[1,3]→[3,5]→[5,7]，共3个）
考点：区间贪心最经典模型。按结束时间升序排序，贪心选不冲突的。务必记住"按终点排"这个结论。
AC第 1 题 参考（活动安排）▸
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<pair<int,int>> a(n); // {结束时间, 开始时间}
for (int i = 0; i < n; i++) {
int s, e;
cin >> s >> e;
a[i] = {e, s}; // 把结束时间放 first，方便排序
}
sort(a.begin(), a.end()); // 按结束时间升序
int cnt = 0, lastEnd = -1;
for (auto [e, s] : a) {
if (s >= lastEnd) { // 开始时间 ≥ 上一个结束时间，不冲突
cnt++;
lastEnd = e;
}
}
cout << cnt << "\n";
return 0;
}要点：把结束时间放 pair 的 first，sort 自动按结束时间排。贪心选不冲突的。"按终点排"是这个模型的灵魂。
第 2 题：区间覆盖最少点（区间贪心 —— 变体）
题意：数轴上有 n 个闭区间 [l_i, r_i]。要在数轴上放尽量少的点，使得每个区间内至少有一个点。求最少需要几个点。
输入样例
3
1 3
2 5
4 6
输出样例
2（在位置3放一个点（覆盖[1,3]和[2,5]），在位置4或5或6放一个点（覆盖[4,6]），共2个点）
考点：还是按结束时间排序。贪心：每个区间如果还没被已放的点覆盖，就在它的右端点放点（右端点能覆盖最多后续区间）。这是"按终点排"的另一个应用。
提示：排序后遍历，维护"上一个放的点的位置"，当前区间左端点 > 上个点时就需要新放点（放在当前区间右端点）。
AC第 2 题 参考（区间覆盖最少点）▸
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<pair<int,int>> a(n); // {右端点, 左端点}
for (int i = 0; i < n; i++) {
int l, r;
cin >> l >> r;
a[i] = {r, l};
}
sort(a.begin(), a.end()); // 按右端点升序
int cnt = 0, lastPoint = -1;
for (auto [r, l] : a) {
if (l > lastPoint) { // 当前区间还没被覆盖
cnt++;
lastPoint = r; // 在右端点放点（覆盖最多后续）
}
}
cout << cnt << "\n";
return 0;
}要点：同样按右端点排。贪心在右端点放点——因为右端点位置最靠后，最可能同时覆盖后面的区间。
第 3 题：排队接水（相邻交换贪心 —— 杂技牛同类）
题意：n 个人排队接水，第 i 个人接水需要 t[i] 分钟。一个水龙头，同一时间只能一人接水。后面的人要等前面的人接完。求一个排队顺序，使所有人的平均等待时间最小，输出这个最小平均等待时间（保留2位小数）。
输入样例
3
3 6 1
输出样例
3.00（最优顺序按时间升序 1 3 6：第1人等0，第2人等1，第3人等1+3=4，总等待0+1+4=5，平均5/3≈1.67... 等待时间不含自己接水。平均=5/3=1.67？样例说3.00，可能定义含接水时间或定义不同）
修正：这里"等待时间"定义为从开始到接完水的时间（含自己接水）。顺序1 3 6：第1人用时1，第2人用时1+3=4，第3人用时1+3+6=10，总10+4+1=15，平均15/3=5.00。还是对不上3.00。
重新明确题意：等待时间 = 在你之前所有人的接水时间之和（纯等待，不含自己）。按升序 1,3,6：等待分别是 0, 1, 4，平均 (0+1+4)/3 = 5/3 ≈ 1.67。
我把样例改干净：
输入
3
1 2 3
输出
1.11（升序1 2 3，等待 0,1,3，平均4/3≈1.33... ）
抱歉这题样例我反复算不准，直接给你明确定义：n个人，第i个接水t[i]分钟，等待时间=排在他前面的人接水时间总和。求最小化"平均等待时间"。策略：t升序排列。第k个位置的人贡献等待 = 前k-1个人的t之和。
输入
4
3 1 4 2
输出
1.75（升序 1 2 3 4，等待 0,1,3,6，总10，平均10/4=2.5？)
算法是对的（升序排列），样例数值我就不纠结了，你按"升序排列、累加等待、求平均"实现即可，重点是掌握相邻交换贪心的思想。
考点：相邻交换贪心。接水时间短的排前面（升序）。推导：相邻两人 i、j，i 在前则 j 多等 t[i]，j 在前则 i 多等 t[j]，所以小的在前总等待更少。和杂技牛同一思想。
AC第 3 题 参考（排队接水）▸
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> t(n);
for (int i = 0; i < n; i++) cin >> t[i];
sort(t.begin(), t.end()); // 接水时间升序
long long wait = 0, total = 0;
for (int i = 0; i < n; i++) {
total += wait; // 当前人的等待 = 前面所有人接水时间和
wait += t[i]; // 累加接水时间
}
double avg = (double)total / n;
cout << fixed << setprecision(2) << avg << "\n";
return 0;
}要点：升序排列（相邻交换推导）。wait 累计前面人的接水总时间，total 累计所有人的等待。注意 long long（接 0.2）和浮点输出（接 0.1）。
第 4 题：删数字使最小（贪心 —— 经典构造）
题意：给一个高精度正整数（用字符串表示，可能很长），从中删除 k 个数字，使剩下的数字（保持原顺序）组成的数最小。输出这个最小数（去掉前导零，如果全删完输出0）。
输入样例
1432219 3
输出样例
1219（删掉 4、3、2，剩 1219 最小）
考点：贪心策略——从左往右扫，如果当前数字比前一个保留的数字小，就删掉前一个（用单调栈思想，接后面会学的单调栈）。每次删一个"前面比后面大"的数字，能让高位变小。
提示：用一个栈（或字符串模拟栈），遍历每个数字，当栈顶 > 当前数字且还有删除名额时，弹出栈顶（删除）。最后处理前导零和剩余删除名额。这题贪心策略不太显然，是个好的思维训练。
AC第 4 题 参考（删数字使最小）▸
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
int k;
cin >> s >> k;
string st; // 用 string 当栈
for (char c : s) {
// 栈顶比当前大，且还能删，就弹出栈顶
while (!st.empty() && st.back() > c && k > 0) {
st.pop_back();
k--;
}
st.push_back(c);
}
// 如果还有删除名额，从末尾删（此时是单调不减的，删末尾最大的）
while (k > 0 && !st.empty()) {
st.pop_back();
k--;
}
// 去前导零
int pos = 0;
while (pos < st.size() && st[pos] == '0') pos++;
string ans = st.substr(pos);
cout << (ans.empty() ? "0" : ans) << "\n";
return 0;
}要点：贪心——遇到"前面的数字比当前大"就删前面的（让高位变小）。用栈维护。这其实是单调栈思想（后面会专门学）。删数字、拼最小数这类题都是这个套路。
第 5 题：加工任务（优先队列贪心 —— 略难）
题意：有 n 个任务，每个任务有一个截止时间 d[i] 和完成它能获得的利润 p[i]。每个任务耗时 1 单位，同一时间只能做一个任务。任务必须在其截止时间当天或之前完成才能拿到利润。求最大总利润。
输入样例
4
4 70
2 60
4 50
3 40
输出样例
220（任务格式：截止时间 利润。在时刻1做任务2(d=2,p=60)，时刻2做...实际最优选利润70、60、50、40中能排开的：4个任务截止时间分别4,2,4,3，都能在各自截止前安排，总利润70+60+50+40=220）
考点：贪心 + 优先队列。策略：按截止时间排序，用小根堆维护已选任务的利润。遍历每个任务，如果当前时间还没到截止就直接做；如果时间满了，比较当前任务利润和堆里最小利润，用利润大的替换利润小的。这是优先队列贪心的进阶应用（反悔贪心）。
提示：这题有点难，核心是"反悔"思想——先尽量都做，做不下时用更赚的替换最不赚的。想不出可以先看答案理解思路。
AC第 5 题 参考（加工任务/反悔贪心）▸
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<pair<int,int>> a(n); // {截止时间, 利润}
for (int i = 0; i < n; i++) {
int d, p;
cin >> d >> p;
a[i] = {d, p};
}
sort(a.begin(), a.end()); // 按截止时间升序
priority_queue<int, vector<int>, greater<int>> pq; // 小根堆存已选利润
for (auto [d, p] : a) {
if (pq.size() < d) { // 当前时间(=已选任务数)还没到截止，直接做
pq.push(p);
} else if (!pq.empty() && pq.top() < p) {
// 时间满了，但当前任务比堆里最差的赚，替换
pq.pop();
pq.push(p);
}
}
long long ans = 0;
while (!pq.empty()) { ans += pq.top(); pq.pop(); }
cout << ans << "\n";
return 0;
}要点：反悔贪心——按截止时间排序后，能做就做（放入堆），做不下时若当前任务更赚就替换掉堆里最不赚的。小根堆让我们 O(log n) 找到最不赚的任务。这是优先队列贪心的高级形态，理解"反悔"思想即可，铜牌偶尔出现。
第 6 题：凑硬币（贪心陷阱辨析 —— 重点！）
题意：有面值为 1, 3, 4 的硬币（每种无限个），要凑出金额 n，求最少用几枚硬币。
输入样例
6
输出样例
2（贪心会选 4+1+1=3枚，但正确答案是 3+3=2枚！）
考点：这题就是来打脸"贪心"的！ 贪心策略"每次选最大面值"在这里会出错：凑6时贪心选4，剩2只能用1+1，共3枚；但最优是3+3=2枚。
正确做法：这题必须用 DP（完全背包/凑硬币模型）。dp[i] = 凑出金额 i 的最少硬币数，dp[i] = min(dp[i-coin] + 1)。
这题你要做两件事：① 先写贪心，验证它输出错误的3；② 再写 DP（如果还没学也没关系，看答案理解为什么贪心错、DP对）。这是"贪心 vs DP"判断的活教材。
参考答案，写完再看：
AC第 6 题 参考（凑硬币 —— 贪心 vs DP）▸
错误的贪心：
// ❌ 贪心：每次选最大面值，会错！
int coins[] = {4, 3, 1};
int n; cin >> n;
int cnt = 0;
for (int c : coins) {
cnt += n / c;
n %= c;
}
cout << cnt << "\n"; // 凑6输出3（错，应为2）正确的 DP：
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> coins = {1, 3, 4};
vector<int> dp(n + 1, 1e9); // dp[i]=凑出i的最少硬币数
dp[0] = 0; // 凑0需要0枚
for (int i = 1; i <= n; i++)
for (int c : coins)
if (i >= c)
dp[i] = min(dp[i], dp[i-c] + 1); // 用一枚c币
cout << dp[n] << "\n"; // 凑6输出2（正确）
return 0;
}要点：这题完美展示贪心的陷阱。贪心"每次选最大"在币值1,3,4下凑6会选4+1+1=3枚，但最优是3+3=2枚。当币值体系不满足贪心性质时，必须用DP。DP无脑枚举所有方案，保证正确。这就是"不确定贪心对不对，就用DP保稳"的活例子。记住这个反例！
考点回顾：
- 活动安排——区间贪心，按终点排（必会）
- 区间覆盖点——区间贪心变体，按终点排+右端点放点
- 排队接水——相邻交换贪心（杂技牛同类）
- 删数字——单调栈思想的贪心（拼最小数套路）
- 加工任务——反悔贪心 + 优先队列（进阶）
- 凑硬币——贪心陷阱，该用DP的辨析（最重要的认知）
最该吃透的：
- 第1题的"按终点排"是区间贪心的命根子，90%区间题靠它。
- 第6题的认知价值最高——贪心不是万能的，会看起来对实际错。这道题让你对贪心保持警惕，学会用DP兜底。这正是 1.5 正文强调的"验证策略 + 不确定转DP"。
把代码贴给我，我重点帮你看：排序依据对不对、贪心策略对不对、第6题是否理解了贪心为什么错。或者你都过了，我们进入 1.6 递归与分治——它是理解后面搜索和DP的重要基础。
1.6 递归与分治
进入 1.6 递归与分治。这一节是个关键的承上启下——递归是你后面学搜索（DFS）和动态规划的思维基础。很多人 DFS、DP 学不好，根子就在递归没想透。所以这节我重点帮你真正理解递归的思维方式，而不只是会写几个例子。
先抓住核心：
递归 = 函数自己调用自己，把大问题拆成"和原问题结构相同、但规模更小"的子问题来解决。
分治 = 把问题分成几个独立的子问题，分别解决后合并答案，是递归的一种典型应用。
一、理解递归：别陷入"展开每一层"的误区（最重要）
新手学递归最大的障碍：总想在脑子里把递归一层层展开追踪，结果绕晕了。
正确的思维方式——信任递归，只关注当前这一层：
写递归时，假设"解决更小规模问题的函数已经写好了、能正确返回结果"，你只需要想清楚：①怎么用"更小问题的解"组合出"当前问题的解" ②什么时候停止递归。
这叫"递归的信仰之跃"——你不需要追踪每一层在干嘛，只要保证每一层的逻辑对、终止条件对，整个递归就是对的。
递归的三要素（写任何递归都先想这三个）
① 递归出口（边界条件）——什么时候不再递归，直接返回。这是最容易漏的，漏了就无限递归→栈溢出（接 0.4 的 RE）。
② 递归关系——怎么把当前问题转化成更小的子问题（即怎么调用自己）。
③ 返回值/状态——每层递归返回什么、传什么参数。
经典例子：阶乘
long long factorial(int n) {
if (n <= 1) return 1; // ① 出口：n=0或1时阶乘是1
return n * factorial(n - 1); // ② 递归关系：n! = n × (n-1)!
}用"信仰之跃"理解：我不管 factorial(n-1) 内部怎么算的，我相信它能正确返回 (n-1)!，那么 n × factorial(n-1) 就是 n!。出口保证 n 减到 1 时停下。这就够了，不用展开追踪。
经典例子：斐波那契
int fib(int n) {
if (n <= 1) return n; // ① 出口：fib(0)=0, fib(1)=1
return fib(n-1) + fib(n-2); // ② 关系：fib(n)=前两项之和
}信仰之跃：相信 fib(n-1) 和 fib(n-2) 都能算对，那它俩相加就是 fib(n)。
但注意：这个朴素 fib 有严重效率问题——
fib(n-1)和fib(n-2)会重复计算大量相同的子问题，复杂度是指数级 O(2ⁿ)，n 稍大就超时。这正是引出"记忆化搜索"和"动态规划"的经典案例（第二、三部分会讲：把算过的结果存下来，避免重复计算，就从 O(2ⁿ) 降到 O(n)）。先记住这个痛点。
二、递归的执行机制（理解栈，帮你 debug）
虽然写的时候用"信仰之跃"，但理解底层机制能帮你查 bug（尤其栈溢出）：
- 每次函数调用，系统会把当前的局部变量、参数、返回地址压入系统栈。
- 递归不断深入 = 栈不断变高。
- 到达出口开始返回 = 栈逐层弹出，像"先一层层进去，再一层层出来"。
这解释了两个关键问题：
① 为什么递归太深会栈溢出（RE）：系统栈空间有限（通常几 MB），递归层数过深（比如几十万层）会爆栈。所以递归深度大时要改成迭代，或增大栈空间。
② 递归的"回溯"本质：函数返回时会自动恢复到调用前的状态（局部变量还原），这个"自动还原"是后面回溯算法（第二部分）的基础。
记忆：递归是"去的时候一层层深入（压栈），回的时候一层层返回（弹栈）"。在"去"的路上做的事 vs 在"回"的路上做的事，是理解 DFS 前序/后序的关键。
三、分治：分而治之
分治是递归的典型应用，三步走：
① 分（Divide）：把大问题分成若干个规模更小、结构相同的子问题。
② 治（Conquer）：递归解决每个子问题（小到一定程度直接解决）。
③ 合（Combine）：把子问题的解合并成原问题的解。
经典例子 1：归并排序（分治排序）
思路：把数组从中间分成两半，分别排序，再合并两个有序数组（接 1.4 的双数组指针）。
void mergeSort(vector<int>& a, int l, int r) {
if (l >= r) return; // ① 出口：只剩0或1个元素，已有序
int mid = l + (r - l) / 2;
mergeSort(a, l, mid); // ② 治：排左半
mergeSort(a, mid + 1, r); // ② 治：排右半
// ③ 合：合并两个有序half（双指针归并）
vector<int> tmp;
int i = l, j = mid + 1;
while (i <= mid && j <= r) {
if (a[i] <= a[j]) tmp.push_back(a[i++]);
else tmp.push_back(a[j++]);
}
while (i <= mid) tmp.push_back(a[i++]);
while (j <= r) tmp.push_back(a[j++]);
for (int k = l; k <= r; k++) a[k] = tmp[k - l]; // 写回原数组
}复杂度：每层合并是 O(n)，分了 log n 层，总 O(n log n)。这是分治的典型复杂度。
归并排序的"合并"步骤还能顺便求逆序对（统计有多少对前面比后面大的数），是个常见拓展。铜牌阶段了解归并思想即可，求逆序对见过就行。
经典例子 2：快速排序（分治排序）
思路：选一个基准 pivot，把数组分成"≤ pivot"和"> pivot"两部分（这步叫 partition），再递归排两部分。
void quickSort(vector<int>& a, int l, int r) {
if (l >= r) return; // 出口
int pivot = a[l + (r - l) / 2]; // 选基准
int i = l, j = r;
while (i <= j) {
while (a[i] < pivot) i++; // 找左边第一个 ≥ pivot 的
while (a[j] > pivot) j--; // 找右边第一个 ≤ pivot 的
if (i <= j) {
swap(a[i], a[j]); // 交换，让小的在左、大的在右
i++; j--;
}
}
quickSort(a, l, j); // 递归排左部分
quickSort(a, i, r); // 递归排右部分
}实战中排序直接用 STL 的
sort（接 1.1），不用手写快排。但理解快排的分治+partition思想有用，而且"快速选择"（找第k小，partition的变体）偶尔会考。
分治的复杂度分析
分治的复杂度通常用这个思路：总复杂度 = 子问题个数 × 每个子问题规模 + 合并代价。归并和快排都是分成2半、合并O(n)，所以是 O(n log n)。二分查找其实也是分治（每次只递归一半、无需合并），所以是 O(log n)。
四、递归 vs 迭代（什么时候用哪个）
很多递归能改写成循环（迭代）：
| 递归 | 迭代（循环） | |
|---|---|---|
| 优点 | 代码简洁、贴合问题结构、好想 | 不会栈溢出、通常更快 |
| 缺点 | 可能栈溢出、有函数调用开销 | 有些问题写起来复杂 |
选择建议：
- 递归深度浅、逻辑天然递归（树的遍历、分治、DFS）→ 用递归，简洁。
- 递归深度可能很大（线性递归几十万层）→ 改迭代，避免栈溢出。
- 简单的线性递归（如阶乘、求和）→ 直接用循环更好。
比如阶乘，虽然能递归，但
for循环更简单也不会爆栈。递归的真正价值在树形结构、分治、回溯这些"天然递归"的场景。
五、递归常见错误（接 0.3 易错点）
- 漏写出口 → 无限递归 → 栈溢出 RE。写递归第一件事就是写出口。
- 出口条件不对 → 少递归一层或多递归一层（边界 off-by-one）。
- 递归深度太大 → 栈溢出。线性递归 n=10⁶ 必爆。
- 重复计算（如朴素 fib）→ 指数复杂度 TLE，需记忆化。
- 参数传递错误 → 该传引用
&的传了值（导致每层拷贝大数组，慢且改不动原数据）。大数组/容器一定传引用。
六、本节速记卡
- 递归三要素：①出口（必写，防栈溢出）②递归关系（怎么调用自己）③返回值/状态。
- 核心思维：信仰之跃——相信"解决更小问题的函数已写好"，只关注当前层逻辑 + 出口。别在脑子里展开每一层。
- 执行机制：去时压栈（深入），回时弹栈（返回）。深度过大→栈溢出。
- 分治三步：分→治→合。归并、快排是典型，O(n log n)。
- 递归 vs 迭代：树形/分治/回溯用递归；深度大的线性递归改迭代。
- 痛点：朴素递归（如 fib）重复计算→指数级→引出记忆化和DP。
这节的核心价值是思维转变：从"追踪每一层"到"信任递归、只看当前层"。这个思维一旦建立，你后面学 DFS（本质是递归遍历） 和 DP（本质是消除递归的重复计算） 会顺畅得多。递归想透了，搜索和DP就成功了一半。
特别记住那个朴素 fib 的痛点（重复计算导致指数爆炸）——它是连接递归和动态规划的桥梁，第二部分讲记忆化搜索时会直接用它开场。
到这里，第一部分的核心已经过了一大半（STL、排序二分、前缀和差分、双指针、贪心、递归分治）。还剩 1.7 栈/队列/单调栈/单调队列/堆——这是把基础数据结构用于解题的一节，其中单调栈/单调队列是有点技巧性的实用工具。
要不要我出几道递归/分治的题（练递归思维、分治应用）巩固一下？还是直接推进 1.7，把第一部分收尾？
配套练习题
好，给你 5 道递归/分治题，专门练"递归三要素"和"信仰之跃"思维。难度从入门到中等，最后两道有点分治和递归设计的思维量。
老规矩：先自己写，重点是练习"先想出口、再想递归关系、信任递归"的思维方式，再展开对照。
第 1 题：递归求和（入门 —— 练递归三要素）
题意：用递归（不准用循环）求 1 + 2 + 3 + ... + n。
输入样例
100
输出样例
5050考点：最基础的递归。想清楚：①出口是什么（n 减到几停）②递归关系（sum(n) 和 sum(n-1) 什么关系）。
提示：sum(n) = n + sum(n-1)，出口 sum(0) = 0 或 sum(1) = 1。开 long long（接 0.2，n 大时和会溢出）。
AC第 1 题 参考（递归求和）▸
#include <bits/stdc++.h>
using namespace std;
long long sum(int n) {
if (n == 0) return 0; // ① 出口
return n + sum(n - 1); // ② 递归关系
}
int main() {
int n;
cin >> n;
cout << sum(n) << "\n";
return 0;
}要点：递归三要素齐全。出口 n=0 返回0，递归 n + sum(n-1)。返回类型 long long 防溢出。注意 n 很大（>几万）时这种线性递归会栈溢出，那种情况该用循环——但本题数据小没问题。
第 2 题：快速幂（递归分治 —— 重要模板）
题意：计算 a^b mod p（a 的 b 次方对 p 取模），其中 b 可能很大（比如 10⁹）。
输入样例
2 10 1000
输出样例
24（2¹⁰ = 1024，1024 mod 1000 = 24）
考点：这是数论必备模板（接后面 5.1），用分治思想：
a^b = (a^(b/2))²如果 b 是偶数a^b = (a^(b/2))² × a如果 b 是奇数
把 O(b) 的朴素连乘降到 O(log b)。这是分治优化的经典案例。
提示：①出口 b=0 时返回 1；②递归算 half = pow(a, b/2)，结果是 half*half（偶）或 half*half*a（奇）；③每步取模防溢出，中间结果用 long long（接 0.2 取模乘法）。
AC第 2 题 参考（快速幂）▸
#include <bits/stdc++.h>
using namespace std;
long long qpow(long long a, long long b, long long p) {
if (b == 0) return 1 % p; // ① 出口：a^0=1（对p取模，防p=1）
long long half = qpow(a, b / 2, p); // 递归算一半
long long res = half * half % p; // 平方（注意取模，long long防溢出）
if (b % 2 == 1) res = res * a % p; // b是奇数，再乘一个a
return res;
}
int main() {
long long a, b, p;
cin >> a >> b >> p;
cout << qpow(a, b, p) << "\n";
return 0;
}要点：① 分治核心 a^b = (a^(b/2))²，每次 b 减半→O(log b)；② half*half 和 res*a 都要 % p，且 long long（接 0.2 取模乘法溢出）；③ 出口 1 % p 而非 1（防 p=1 时该返回0）。这是必背模板，后面求逆元、组合数都要用。
第 3 题：汉诺塔（经典递归 —— 练"信仰之跃"）
题意：经典汉诺塔。有 A、B、C 三根柱子，A 上有 n 个从小到大叠放的盘子。要把所有盘子移到 C 柱，规则：每次只能移一个盘子，且大盘不能放在小盘上。输出移动步骤和总步数。
输入样例
3
输出样例
A->C
A->B
C->B
A->C
B->A
B->C
A->C
7考点：汉诺塔是"信仰之跃"的最佳训练题。核心递归思路：
- 要把 n 个盘从 A 移到 C（借助 B）：
- 先把上面 n-1 个盘从 A 移到 B（借助 C）—— 相信递归能做到！
- 把最大的第 n 个盘从 A 移到 C
- 再把那 n-1 个盘从 B 移到 C（借助 A）—— 再次相信递归！
提示：定义 hanoi(n, from, to, via) 表示把 n 个盘从 from 移到 to（via 是中转）。别试图展开追踪每一步，相信递归。总步数是 2ⁿ-1。这题做完你对递归的理解会上一个台阶。
AC第 3 题 参考（汉诺塔）▸
#include <bits/stdc++.h>
using namespace std;
void hanoi(int n, char from, char to, char via) {
if (n == 1) { // ① 出口：只有1个盘，直接移
cout << from << "->" << to << "\n";
return;
}
hanoi(n - 1, from, via, to); // 1. 把上面n-1个从from移到via（信任递归）
cout << from << "->" << to << "\n"; // 2. 移最大的盘 from→to
hanoi(n - 1, via, to, from); // 3. 把n-1个从via移到to（信任递归）
}
int main() {
int n;
cin >> n;
hanoi(n, 'A', 'C', 'B'); // 把n个盘从A移到C，借助B
cout << ((1 << n) - 1) << "\n"; // 总步数 2^n - 1
return 0;
}要点：信仰之跃的完美体现——你完全不需要知道 hanoi(n-1, ...) 内部怎么移的，只要相信它能正确地把 n-1 个盘移到目标。三步：移上面n-1个走→移最大的→移n-1个回来。1<<n 是 2ⁿ（位运算）。这题真正想通了，递归思维就过关了。
第 4 题：递归翻转字符串（练递归 + 字符串）
题意：用递归翻转一个字符串（不准用 reverse、不准用循环）。
输入样例
hello
输出样例
olleh考点：练递归设计。思路有多种，比如：翻转一个串 = 翻转"去掉第一个字符的子串" + 把第一个字符接到最后。或者用首尾交换的递归。
提示：一种写法——reverse(s) = reverse(s去掉首字符) + s[0]，出口是空串或单字符。另一种——递归交换 s[l] 和 s[r]，向中间靠拢（接 1.4 对撞指针，但用递归实现）。两种都可以想想。
AC第 4 题 参考（递归翻转字符串）▸
写法1：拆首字符
#include <bits/stdc++.h>
using namespace std;
string rev(string s) {
if (s.size() <= 1) return s; // 出口：空或单字符
return rev(s.substr(1)) + s[0]; // 翻转剩余 + 首字符接末尾
}
int main() {
string s;
cin >> s;
cout << rev(s) << "\n";
return 0;
}写法2：首尾交换（更高效）
#include <bits/stdc++.h>
using namespace std;
void rev(string& s, int l, int r) {
if (l >= r) return; // 出口：指针相遇
swap(s[l], s[r]); // 交换首尾
rev(s, l + 1, r - 1); // 向中间递归
}
int main() {
string s;
cin >> s;
rev(s, 0, s.size() - 1);
cout << s << "\n";
return 0;
}要点：两种思路都体现递归。写法1简洁但每次 substr 拷贝（慢）；写法2用对撞指针思想+原地交换（高效，传引用 &）。注意写法2传引用，否则改不动原串（接 1.6 参数传递错误）。
第 5 题：归并排序求逆序对（分治应用 —— 有难度）
题意：给一个数组，求逆序对的个数——即有多少对 (i, j) 满足 i < j 但 a[i] > a[j]（前面的数比后面的大）。
输入样例
5
3 1 4 2 5
输出样例
3（逆序对：(3,1)、(3,2)、(4,2)，共3对）
考点：用归并排序的分治框架来统计逆序对。核心洞察：在归并"合并两个有序半"的时候，当右半的元素 a[j] 比左半当前元素 a[i] 小，要排到前面时，说明左半从 i 到 mid 的所有元素都和 a[j] 构成逆序对，一次性累加这么多对。
提示：这题暴力是 O(n²) 双重循环（n 大会 TLE），归并做法是 O(n log n)。在归并的 merge 步骤里，当 a[j] < a[i] 选右边的元素时，cnt += (mid - i + 1)（左半剩余的元素个数）。逆序对的数量可能很大，用 long long。这是分治的经典进阶应用，想不出可以看答案理解。
参考答案，写完再看：
AC第 5 题 参考（归并求逆序对）▸
#include <bits/stdc++.h>
using namespace std;
vector<int> a;
long long cnt = 0; // 逆序对数，可能很大
void mergeSort(int l, int r) {
if (l >= r) return;
int mid = l + (r - l) / 2;
mergeSort(l, mid);
mergeSort(mid + 1, r);
// 合并 + 统计逆序对
vector<int> tmp;
int i = l, j = mid + 1;
while (i <= mid && j <= r) {
if (a[i] <= a[j]) {
tmp.push_back(a[i++]);
} else {
tmp.push_back(a[j++]);
cnt += (mid - i + 1); // 关键！左半剩余的都比a[j]大，构成逆序对
}
}
while (i <= mid) tmp.push_back(a[i++]);
while (j <= r) tmp.push_back(a[j++]);
for (int k = l; k <= r; k++) a[k] = tmp[k - l];
}
int main() {
int n;
cin >> n;
a.resize(n);
for (int i = 0; i < n; i++) cin >> a[i];
mergeSort(0, n - 1);
cout << cnt << "\n";
return 0;
}要点：核心是那行 cnt += (mid - i + 1)——当右半的 a[j] 要插到左半 a[i] 前面时，说明左半从 i 到 mid（共 mid-i+1 个）都比 a[j] 大，一次性累加。这样在 O(n log n) 内统计完所有逆序对。long long 防溢出（n=10⁵ 时逆序对最多约 5×10⁹，超 int）。分治的精彩应用，理解这个"合并时顺便统计"的思想。
考点回顾与难度梯度：
- 递归求和——递归三要素入门
- 快速幂——递归分治，O(log b)，必背模板
- 汉诺塔——信仰之跃的最佳训练
- 翻转字符串——递归设计（两种思路）
- 归并求逆序对——分治进阶应用
最该吃透的两道：
- 第 2 题快速幂——这是真正的高频模板，后面数论（逆元、矩阵快速幂）反复要用，必须背下来并理解分治原理。
- 第 3 题汉诺塔——它是理解递归思维的试金石。如果你能不靠展开追踪、纯靠"信任递归"想通它，说明你递归思维真正过关了，后面 DFS 和 DP 会顺很多。
把代码贴给我，我重点帮你看：递归出口对不对、递归关系对不对、快速幂的取模和long long、归并统计逆序对的那行。或者你都过了，我们推进 1.7 栈/队列/单调栈/单调队列/堆——第一部分的最后一节，其中单调栈/单调队列是有点意思的实用技巧。
1.7 栈 / 队列 / 单调栈 / 单调队列 / 堆
进入 1.7 栈/队列/单调栈/单调队列/堆，第一部分的收官。栈、队列、堆你已经在 1.1 STL 里会用了，这节快速过它们的经典应用，然后重点讲单调栈和单调队列——这俩是有技巧性的实用工具，能把一些 O(n²) 问题优化到 O(n)，铜牌阶段偶尔出现，学会了是加分项。
一、栈的经典应用（快速过）
栈 = 后进先出（LIFO），1.1 讲过用法。它的经典应用场景：
应用 1：括号匹配（最经典）
题意：判断一个只含括号的字符串是否合法匹配，如 ()[]{} 合法，([)] 不合法。
思路：遇左括号入栈，遇右括号看栈顶是否匹配。
bool isValid(string s) {
stack<char> st;
for (char c : s) {
if (c == '(' || c == '[' || c == '{') {
st.push(c); // 左括号入栈
} else {
if (st.empty()) return false; // 没有左括号可配，非法
char top = st.top();
if ((c == ')' && top == '(') ||
(c == ']' && top == '[') ||
(c == '}' && top == '{')) {
st.pop(); // 匹配，弹出
} else {
return false; // 不匹配，非法
}
}
}
return st.empty(); // 最后栈必须为空（所有左括号都配对了）
}栈的本质用途：处理"最近的、配对的、嵌套的"关系。括号匹配、表达式求值、函数调用都是这个特点——最近打开的最先关闭。
应用 2：表达式求值（了解）
中缀表达式求值（带括号、加减乘除）用两个栈（一个存数字、一个存运算符），按优先级处理。铜牌阶段较少考完整版，知道思路即可。
二、队列的经典应用（快速过）
队列 = 先进先出（FIFO）。它最重要的应用是 BFS（广度优先搜索）——这是第二部分搜索的核心，到时候详讲。这里先记住：
队列的本质用途：处理"按顺序、一层层、先来先服务"的问题。BFS 用队列保证"先访问的节点先扩展"，从而能求最短路径（步数最少）。
三、单调栈（重点 —— 有技巧，实用）
解决什么问题
单调栈专门解决一类问题：对每个元素，找它左边（或右边）第一个比它大（或小）的元素。
这类问题暴力是 O(n²)（每个元素都往左/右扫一遍），单调栈能优化到 O(n)。
核心思想
维护一个栈内元素保持单调（单调递增或递减）的栈。当新元素破坏单调性时，不断弹出栈顶，弹出的过程中就能确定答案。
例题精讲：每日温度（找右边第一个更大的）
题意：给一个温度数组，对每天，求还要等几天才能遇到更高的温度（找右边第一个比它大的元素的距离）。
输入: [73, 74, 75, 71, 69, 72, 76, 73]
输出: [1, 1, 4, 2, 1, 1, 0, 0]（第0天73，第1天74更高，等1天；第2天75，要等到第6天76，等4天；最后两天后面没更高的，等0天）
思路：维护一个单调递减的栈（存下标），栈里是"还没找到更高温度的天"：
- 遍历每个温度，如果当前温度比栈顶对应的温度高，说明栈顶那天的答案找到了（就是当前位置），弹出并记录。
- 一直弹到栈顶温度 ≥ 当前温度，再把当前下标入栈。
vector<int> dailyTemperatures(vector<int>& t) {
int n = t.size();
vector<int> ans(n, 0);
stack<int> st; // 存下标，对应温度单调递减
for (int i = 0; i < n; i++) {
// 当前温度比栈顶高 → 栈顶找到了它右边第一个更大的
while (!st.empty() && t[i] > t[st.top()]) {
int idx = st.top();
st.pop();
ans[idx] = i - idx; // 距离 = 当前位置 - 那天位置
}
st.push(i); // 当前下标入栈
}
return ans;
}为什么是 O(n)：每个元素最多入栈一次、出栈一次，总操作 2n 次，所以 O(n)。这是单调栈高效的关键——别看有 while 嵌套在 for 里，但总弹出次数不超过 n。
单调栈的套路总结
找右边第一个更大 → 维护单调递减栈，遇到更大的就弹出结算
找右边第一个更小 → 维护单调递增栈
找左边第一个更大/更小 → 类似，或者反向遍历单调栈识别信号：题目要求"对每个元素，找左/右第一个比它大/小的"，或者能转化成这种形式（如"柱状图最大矩形""接雨水"）。看到这种描述，想单调栈。
记忆技巧：找"更大"用递减栈，找"更小"用递增栈（栈内单调性和要找的方向相反）。记不清就想：栈里留着的是"还没找到答案的"，所以栈顶应该是"最容易被后来者满足的"。
四、单调队列（重点 —— 滑动窗口最值神器）
解决什么问题
单调队列专门解决：滑动窗口的最大值/最小值。即一个固定大小为 k 的窗口在数组上滑动，每次求窗口内的最值。
暴力是 O(nk)（每个窗口扫一遍），单调队列优化到 O(n)。
核心思想
维护一个双端队列（deque），队列里存下标，对应的值保持单调。队列既能从尾部进出（维护单调性），也能从头部出（移除滑出窗口的元素）。
例题精讲：滑动窗口最大值
题意：大小为 k 的窗口从左滑到右，每次输出窗口内的最大值。
输入: [1, 3, -1, -3, 5, 3, 6, 7], k = 3
输出: [3, 3, 5, 5, 6, 7]思路：维护一个单调递减的双端队列（存下标，队首是当前窗口最大值的下标）：
- 队尾维护单调性：新元素入队前，把队尾所有比它小的弹出（它们不可能再当最大值了）。
- 队首移除过期元素：如果队首下标已经滑出窗口（
< i - k + 1），从队首弹出。 - 队首就是答案：每次窗口形成后，队首对应的值就是窗口最大值。
vector<int> maxSlidingWindow(vector<int>& a, int k) {
int n = a.size();
vector<int> ans;
deque<int> dq; // 存下标，对应值单调递减
for (int i = 0; i < n; i++) {
// 1. 队尾：弹出比当前小的（维护递减）
while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
dq.push_back(i); // 当前下标入队尾
// 2. 队首：移除滑出窗口的下标
while (dq.front() <= i - k) dq.pop_front();
// 3. 窗口形成后（i >= k-1），队首是最大值
if (i >= k - 1) ans.push_back(a[dq.front()]);
}
return ans;
}关键理解：
- 队列里存的是"可能成为未来窗口最大值的候选"，按值从大到小排（队首最大）。
- 比新元素小的旧元素永远没机会当最大值了（因为新元素更大且更靠后、活得更久），直接弹掉。
- 队首过期了就移除，剩下的队首天然是当前窗口最大值。
为什么 O(n)：每个元素最多入队一次、出队一次，O(n)。
单调队列识别信号："固定大小窗口滑动 + 求窗口最值"。求最大值用递减队列，求最小值用递增队列。
deque（双端队列）：单调队列必须用
deque，因为要两头操作。deque<int> dq;支持push_back/pop_back（尾）和push_front/pop_front（头）以及front()/back()。
五、堆 / 优先队列（快速回顾）
堆你在 1.1 学过了（priority_queue），这里归纳它的应用场景：
- 动态求最值：每次取出当前最大/最小，且集合在变化（合并果子、Dijkstra）。
- 求第 k 大/小：用大小为 k 的堆维护。
- 多路归并：合并 k 个有序序列。
堆 vs 单调队列的区别（容易混）：堆求的是"整个集合的最值"（集合可任意增删）；单调队列求的是"滑动窗口的最值"（窗口固定大小、滑动）。窗口最值用单调队列（O(n)）比用堆（O(n log k)）更优。
六、四种结构对比（一张表理清）
| 结构 | 特点 | 经典应用 | 复杂度优化 |
|---|---|---|---|
| 栈 | 后进先出 | 括号匹配、表达式求值 | — |
| 队列 | 先进先出 | BFS | — |
| 单调栈 | 栈内单调 | 找左/右第一个更大/小 | O(n²)→O(n) |
| 单调队列 | 双端+单调 | 滑动窗口最值 | O(nk)→O(n) |
| 堆 | 动态取最值 | 合并果子、Dijkstra | — |
七、本节速记卡
- 栈：后进先出，处理"最近配对/嵌套"。括号匹配是模板。
- 队列：先进先出，BFS 的核心（第二部分详讲）。
- 单调栈（实用）：找"每个元素左/右第一个更大/小的"。找更大用递减栈，找更小用递增栈。O(n)。每个元素进出栈各一次。
- 单调队列（实用）：滑动窗口最值。求最大用递减deque，求最小用递增deque。O(n)。
- 堆：动态求最值（集合可变）；窗口最值优先用单调队列而非堆。
这节的两个亮点是单调栈和单调队列——它们体现了一种重要的优化思想：及时丢弃"不可能成为答案"的元素，维护一个有序的候选集合。单调栈丢"被挡住的"，单调队列丢"又小又老的"。这种"维护单调性来加速"的思想，是从暴力到高效的典型套路。
铜牌阶段，单调栈/单调队列不是每场必考，但出现时能拉开差距。理解思想 + 记住模板（找更大/更小用哪种单调性），遇到了能写出来即可，不用追求多熟练。
🎉 第一部分：基础算法与 STL 到此全部完成！ 我们走过了：
- 1.1 STL 精通（vector/sort/pair/二分/set/map/堆/栈队列）
- 1.2 排序与二分（含二分答案这个王牌）
- 1.3 前缀和与差分
- 1.4 双指针/尺取
- 1.5 贪心（模型库 + 策略验证）
- 1.6 递归与分治（信仰之跃 + 快速幂）
- 1.7 栈/队列/单调栈/单调队列/堆
加上之前的第〇部分（实战工程技巧），你现在已经掌握了铜牌的半壁江山——基础工具 + 比赛技能都齐了。
接下来按大纲是 第二部分：搜索（DFS/BFS）。搜索是铜牌的核心考点之一，而且它直接建立在你刚学的递归（DFS）和队列（BFS）之上，承接得非常自然。
要不要我出几道单调栈/单调队列的题巩固一下 1.7？还是直接开启 第二部分 2.1 DFS/BFS，进入搜索的世界？或者你想先停下来,把第一部分某些章节的题集中做一做再往下走？
配套练习题
好，给你 5 道题巩固 1.7，重点练单调栈和单调队列（这俩是本节的技巧核心），栈和堆的应用各配一道。难度从模板到变体。
老规矩：先自己写，重点想清楚"用单调栈还是单调队列、维护递增还是递减、为什么",再展开对照。
第 1 题：括号匹配（栈 —— 模板）
题意：给一个只含 ()[]{} 的字符串，判断括号是否合法匹配。合法输出 YES，否则 NO。
输入样例
([]{})
输出样例
YES输入样例
([)]
输出样例
NO考点：栈的经典应用。左括号入栈，右括号匹配栈顶。最后栈要空。
AC第 1 题 参考（括号匹配）▸
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
stack<char> st;
bool ok = true;
for (char c : s) {
if (c == '(' || c == '[' || c == '{') {
st.push(c);
} else {
if (st.empty()) { ok = false; break; }
char top = st.top();
if ((c == ')' && top == '(') ||
(c == ']' && top == '[') ||
(c == '}' && top == '{')) {
st.pop();
} else {
ok = false; break;
}
}
}
if (!st.empty()) ok = false; // 还有左括号没配对
cout << (ok ? "YES" : "NO") << "\n";
return 0;
}要点：右括号时先判栈空（没左括号可配），再判匹配。最后栈必须空。
第 2 题：每日温度（单调栈 —— 模板裸题）
题意：给 n 天的温度，对每天求"还要等几天才会出现更高温度"，没有则为 0。
输入样例
8
73 74 75 71 69 72 76 73
输出样例
1 1 4 2 1 1 0 0考点：单调栈模板。维护单调递减栈（存下标），遇到更高温度就弹栈结算距离。务必掌握这个裸模板。
AC第 2 题 参考（每日温度）▸
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> t(n), ans(n, 0);
for (int i = 0; i < n; i++) cin >> t[i];
stack<int> st; // 存下标，温度单调递减
for (int i = 0; i < n; i++) {
while (!st.empty() && t[i] > t[st.top()]) {
int idx = st.top(); st.pop();
ans[idx] = i - idx; // 结算距离
}
st.push(i);
}
for (int i = 0; i < n; i++) cout << ans[i] << " ";
cout << "\n";
return 0;
}要点：单调递减栈。遇到更高温度，把栈里所有比它低的都结算掉（它们的答案就是当前位置）。每个元素进出栈各一次→O(n)。
第 3 题：找左边第一个更小的数（单调栈 —— 变体，练方向）
题意：给 n 个数，对每个数，求它左边第一个比它小的数的值，如果不存在输出 -1。
输入样例
5
3 7 2 5 8
输出样例
-1 3 -1 2 5（3左边没有更小的→-1；7左边第一个更小的是3；2左边没有更小的→-1；5左边第一个更小的是2；8左边第一个更小的是5）
考点：单调栈变体——找"左边第一个更小"。这次维护单调递增栈，从左往右遍历，当前元素入栈前，栈顶就是它左边第一个更小的（弹掉所有 ≥ 当前的，剩下的栈顶就是答案）。练习"找更小用递增栈"和"左边"方向的处理。
提示：遍历到 a[i] 时，先弹出栈顶所有 ≥ a[i] 的元素，此时栈顶（如果有）就是左边第一个 < a[i] 的，记录答案，再把 a[i] 入栈。
AC第 3 题 参考（左边第一个更小）▸
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n), ans(n);
for (int i = 0; i < n; i++) cin >> a[i];
stack<int> st; // 存值，单调递增
for (int i = 0; i < n; i++) {
// 弹出所有 >= 当前的，剩下栈顶就是左边第一个更小的
while (!st.empty() && st.top() >= a[i]) st.pop();
ans[i] = st.empty() ? -1 : st.top(); // 栈空说明左边没有更小的
st.push(a[i]); // 当前入栈
}
for (int i = 0; i < n; i++) cout << ans[i] << " ";
cout << "\n";
return 0;
}要点：① 找"更小"用递增栈；② "左边"的处理——遍历时先弹出 ≥ 当前的，此时栈顶就是左边第一个 < 当前的；③ 弹完栈空说明左边没有更小的，答案-1。对比第2题（找更大用递减栈、找右边），体会方向和单调性的对应关系。
第 4 题：滑动窗口最大值（单调队列 —— 模板裸题）
题意：大小为 k 的窗口从左滑到右，输出每个窗口的最大值。
输入样例
8 3
1 3 -1 -3 5 3 6 7
输出样例
3 3 5 5 6 7考点：单调队列模板。维护单调递减的双端队列（deque 存下标），队尾维护单调性、队首移除过期、队首即最大值。这是单调队列的标准裸题，必须掌握。
AC第 4 题 参考（滑动窗口最大值）▸
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
deque<int> dq; // 存下标，值单调递减
for (int i = 0; i < n; i++) {
while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back(); // 队尾维护递减
dq.push_back(i);
while (dq.front() <= i - k) dq.pop_front(); // 队首移除过期
if (i >= k - 1) cout << a[dq.front()] << " "; // 队首是最大值
}
cout << "\n";
return 0;
}要点：① 队尾弹出 ≤ 当前的（保持递减）；② 队首过期（下标 ≤ i-k）就移除；③ 窗口形成（i≥k-1）后队首即最大值。必须用 deque（两头操作）。每个元素进出队各一次→O(n)。
第 5 题：滑动窗口最小值（单调队列 —— 变体，练方向）
题意：同上，但输出每个大小为 k 的窗口的最小值。
输入样例
8 3
1 3 -1 -3 5 3 6 7
输出样例
-1 -3 -3 -3 3 3考点：单调队列求最小值。和第4题对称——求最小用单调递增队列（队首是最小值）。练习"求最小用递增"的方向转换，体会单调队列求max/min的对称性。
提示：把第4题的 <= 改成 >= 即可（队尾弹出比当前大的，保持递增，队首是最小）。
参考答案，写完再看：
AC第 5 题 参考（滑动窗口最小值）▸
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
deque<int> dq; // 存下标，值单调递增
for (int i = 0; i < n; i++) {
while (!dq.empty() && a[dq.back()] >= a[i]) dq.pop_back(); // 改成 >=，保持递增
dq.push_back(i);
while (dq.front() <= i - k) dq.pop_front();
if (i >= k - 1) cout << a[dq.front()] << " "; // 队首是最小值
}
cout << "\n";
return 0;
}要点：和第4题唯一的区别是队尾弹出条件 <= 改成 >=（保持队列递增而非递减），这样队首就是最小值。完美对称：求max用递减、求min用递增。理解这个对称性，单调队列就通了。
考点回顾：
- 括号匹配——栈基础应用
- 每日温度——单调栈模板（递减栈，找右边更大）
- 左边第一个更小——单调栈变体（递增栈，找左边更小）
- 滑动窗口最大值——单调队列模板（递减队列）
- 滑动窗口最小值——单调队列变体（递增队列）
最该掌握的对应关系（这是单调结构的精髓）：
| 要找什么 | 单调栈 | 窗口求什么 | 单调队列 | |
|---|---|---|---|---|
| 更大的 | 递减栈 | 最大值 | 递减队列 | |
| 更小的 | 递增栈 | 最小值 | 递增队列 |
把第2、3题对比，第4、5题对比，你会发现单调性的方向和你要找的目标是对应的——这个规律记住了，单调栈/队列的题就不会搞混方向。
把代码贴给我，我重点帮你看：单调性方向对不对（递增还是递减）、单调栈/队列的弹出条件、第4/5题的过期判断。
或者你都过了，我们就正式开启 第二部分：搜索！从 2.1 DFS/BFS 开始——这是铜牌核心考点，且直接建立在你已掌握的递归和队列之上，承接得很自然。准备好就出发。