ABC447 ACEF题解：双指针、树状数组与线段树边界实战

ABC447 这场打完之后我最大的感受是AtCoder Beginner Contest 系列做到四百多场以后出题人越来越懂怎么用“边界处理”来淘汰人了。A、B 两题基本送分C、D 决定你能不能排进前半区真正让排名拉开差距的其实是 E 和 F。我这次只写 ACEF 四题的题解是因为 B 属于纯模拟D 属于一眼结论题网上随便一搜就是一堆而 A、C、E、F 这条线恰好把“条件边界、双指针边界、离散化边界、线段树区间边界”完整地串了一遍。文章偏实战C17 为主四个题都给了可直接提交的代码想稳定过 ABC 前五题的朋友可以直接照着抄思路再自己敲一遍。1. 先说清楚这场的 ACEF 到底卡在哪里1.1 我的做题顺序与时间分配我打 ABC 的习惯是先花五分钟把 A 秒掉给后面留足心理余量。这场我实际顺序是 A → C → E → FB 和 D 在赛后补题时顺手写了但确实没有太多值得展开的东西。A 题就是一道普通的条件分支题唯一需要注意的是边界值归到哪一档C 题是双指针尺取法求合法子数组数量模板味道很重但没开 long long 的人一大片E 题是逆序对计数树状数组 离散化的教科书题F 题是带懒标记的线段树范围加、范围求和题目本身不绕但代码细节多现场翻车率极高。时间分配上C 题我大概用了 18 分钟其中 10 分钟在想“为什么双指针是对的”真正写代码只用了 8 分钟。E 题 20 分钟F 题花了我 40 分钟其中一半时间在调一个非常愚蠢的懒标记下推问题。这个后面会详细说。1.2 四个题的考点地图题号核心考点典型难度区间复盘评级A条件分支与边界取值ABC A 入门题灰题纯送C双指针 / 尺取法ABC C 中档题茶题必须会E树状数组 / 归并排序ABC E 进阶段绿题模板熟练度F线段树懒标记ABC F 分水岭水蓝题代码功底这张表格是我赛后给这场做评级时顺手整理的。蓝色和绿色之间的差距往往不是“会不会算法”而是“能不能一次写对”。F 题就是典型的例子思路五分钟想完代码半小时调完这在真实比赛里非常常见。2. A 题与 C 题从“边界”开始讲起2.1 A 题一道快乐的条件判断题但别小看顺序题意大致是这样输入一个整数 T-100 ≤ T ≤ 40根据体温输出对应描述T ≥ 30 输出 “Hot”T ≥ 20 输出 “Warm”T ≥ 0 输出 “Cool”否则输出 “Cold”。这道题只要从上到下按顺序判断就不会错#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin T; if (T 30) { cout Hot\n; } else if (T 20) { cout Warm\n; } else if (T 0) { cout Cool\n; } else { cout Cold\n; } return 0; }这里真正容易错的点只有一个边界值属于哪一档。T 30 应该输出 “Hot”T 20 应该输出 “Warm”T 0 应该输出 “Cool”。如果你把条件写成 T 30、T 20、T 0那这三个边界点就会整体错位落到下一档去。AtCoder 的样例通常会故意放一个边界值来筛这种写法所以这种白给题反而要认真看样例。提示判断顺序还有一种写法是先判 Cold 再往上走但那样很容易把冷的边界写反。我个人建议永远从上往下写也就是“大条件先命中小条件做兜底”这样心智负担最小。2.2 C 题双指针为什么能卡进 O(N)C 题意大致是给定长度为 N 的数组 A以及一个上限 K统计有多少个连续子数组满足“区间和不超过 K”。数据范围大概是 N ≤ 2×10^5A_i ≥ 1 都是正整数。看到正整数就要立刻想到双指针。为什么因为所有 A_i 都大于 0区间和是严格单调递增的你往窗口右边加一个数和不降你从窗口左边扔一个数和不增。这一条单调性就是双指针能用的根基。具体做法是右端点 r 从 1 扫到 N每到一个 r先把 A[r] 加进当前窗口和 sum。接下来如果 sum K就不断把左端点 l 往右挪同时从 sum 里减掉 A[l]直到 sum ≤ K 为止。此时以 r 为右端点、左端点落在 [l, r] 内的所有子数组都满足条件数量就是 r - l 1累加到答案里。#include bits/stdc.h using namespace std; using ll long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; ll K; cin N K; vectorll A(N 1); for (int i 1; i N; i) cin A[i]; ll sum 0, ans 0; int l 1; for (int r 1; r N; r) { sum A[r]; while (sum K) { sum - A[l]; l; } ans (ll)(r - l 1); } cout ans \n; return 0; }为什么这个算法是对的关键在于“对于固定的右端点 r合法的左端点永远是从某个位置到 r 的连续一段”。因为区间和随左端点右移单调递减所以要么左端点从 l 到 r 全都合法要么前面有一段不合法后面才合法绝不会出现中间合法、两边不合法的“断开”情况。因此只要维护好当前最小的合法左边界 l答案计算就是 O(1)整体 O(N)。2.3 C 题现场踩坑实录第一坑是 long long。N 最大 2×10^5A_i 最大 10^9一个窗口的 sum 可以到 2×10^14答案最多是 N(N-1)/2 量级也远超 int。我亲眼见过有人 sum 用 int 存样例全过提交直接 WA 一片。这题的 sum 和 ans 都必须开 long long。第二坑是 while 的写法顺序。正确写法是“先减去 A[l]再 l”。有人习惯写成 sum - A[l]效果一样但如果你把 l 写在 sum - A[l] 前面窗口左边界和你减的数字就会错位答案直接乱掉。这种错误在本地往往测不出来因为样例通常很小。第三坑是右端点边界。从 1 开始扫还是从 0 开始扫都行但一定要统一。我习惯用 1-based因为接下来 E、F 题的树状数组和线段树也用 1-based一套习惯到处复用省得每次都要换算下标。3. E 题逆序对计数树状数组和归并排序都能做3.1 题型识别怎么一眼看出是逆序对E 题意大致是给定长度为 N 的数组 A统计有多少对下标 (i, j) 满足 i j 且 A_i A_j。N 最大 2×10^5如果直接双重循环枚举O(N^2) 必炸。只要看到“统计前面有多少个比当前大的数”这种对数形式第一反应就应该是逆序对第二反应就是数据结构优化计数。逆序对这种问题的本质是在从左往右扫描的过程中维护一个“已经见过的数字”的多重集每到一个新元素 A[i]只需要回答“这个集合里有多少个数字严格大于 A[i]”。如果数字范围不大可以直接开值域数组但这里 A_i 最大到 10^9不可能开数组所以要先做离散化把数值映射成相对排名。3.2 树状数组 离散化的完整实现离散化的标准流程是复制一份数组排序去重后得到一个升序的 unique 值列表然后用 lower_bound 把原数组每个值映射成 1 到 M 的排名。映射完之后“严格大于 A[i]”就变成了“排名大于 rk(A[i])”树状数组维护的是每个排名出现的次数。树状数组部分我用一个结构体封装起来查询和更新都是 O(log M)整体复杂度 O(N log N)。#include bits/stdc.h using namespace std; using ll long long; struct BIT { int n; vectorint tree; BIT(int n) : n(n), tree(n 1, 0) {} void add(int idx, int val) { for (; idx n; idx idx -idx) tree[idx] val; } int query(int idx) { int res 0; for (; idx 0; idx - idx -idx) res tree[idx]; return res; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin N; vectorll A(N 1), B(N 1); for (int i 1; i N; i) { cin A[i]; B[i] A[i]; } sort(B.begin() 1, B.end()); vectorll vals; for (int i 1; i N; i) { if (i 1 || B[i] ! B[i - 1]) vals.push_back(B[i]); } auto getRank [](ll x) { return (int)(lower_bound(vals.begin(), vals.end(), x) - vals.begin()) 1; }; BIT bit((int)vals.size()); ll ans 0; for (int i 1; i N; i) { int rk getRank(A[i]); ans (ll)(i - 1 - bit.query(rk)); bit.add(rk, 1); } cout ans \n; return 0; }这里统计用的是“已经插入的前 i-1 个数中排名大于 rk 的个数”。bit.query(rk) 返回的是排名小于等于 rk 的个数所以 i-1 减掉它剩下的就是严格大于 A[i] 的个数。这样写的好处是重复数字不会被误算因为重复值排名相同不会被计入“严格大于”。3.3 归并排序的替代方案如果不想写树状数组归并排序也能计逆序对原理是在合并两个有序区间时如果右边区间的某个数小于左边区间当前指向的数那说明它比左边区间剩余的所有数都小直接累加“左边剩余个数”。复杂度同样是 O(N log N)。我个人的建议是两种方法都要掌握但比赛里优先用树状数组。原因很实际树状数组代码量更小不容易在递归边界上出错而且很多其他问题比如动态第 K 小、统计区间内不同数个数都是在“维护排名出现次数”这个基础上的你练熟 BIT 相当于拿一把武器打十个怪。3.4 E 题最容易栽的四个地方重复数字统计条件写错的话会把等于当前值的数字也当成逆序对。记住逆序对要求严格大于所以查询只能查“排名小于当前排名”或者“总个数减去排名小于等于当前排名”的那种写法千万别混淆。long long逆序对数量上限是 N(N-1)/2 ≈ 2×10^10int 根本装不下。答案、以及一切和答案累加有关的变量都必须用 64 位。树状数组大小要开 unique 之后的 M不是开原 N。虽然开 N 通常也不会越界但如果你把原 N 当排名上界遇到值为最大的元素时 idx 可能超出边界RE 得莫名其妙。lower_bound 之前必须先排序去重如果直接用原数组跑 lower_bound得到的“排名”是乱序的整个统计就废了。这个错我犯过一次查了半小时才发现。4. F 题线段树懒标记实战拆解4.1 为什么不能无脑用前缀和F 题意大致是长度为 N 的数组有 Q 次操作两种类型类型 1 是给区间 [l, r] 内每个数都加上 x类型 2 是查询区间 [l, r] 的和。N 和 Q 都在 2×10^5 级别。如果在没有修改操作的情况下打一个前缀和数组就可以 O(1) 回答区间和。但这里修改操作是“在线”的每次加完前缀和数组全部要重建复杂度 O(NQ)完全不可行。也可以用差分数组做区间加但差分数组只能维护“原始数组的值”查询区间和的时候你还是得把前缀重新加一遍同样退化。所以这类“区间修改 区间查询”的题目标准解法就是线段树 懒标记复杂度 O((NQ) log N)。4.2 懒标记到底在偷什么懒线段树每个节点代表一个区间节点里至少要存两样东西这个区间的和 sum以及一个懒标记 lazy。lazy 的含义是“这个区间整体被加了多少但还没有下传给子节点”。记懒标记的目的是把“整段覆盖”的修改拦在最高层。比如给 [3, 10] 全部加 5如果这个区间正好被某个节点完全包住那我只需要更新这个节点的 sum 和 lazy根本不用递归到叶子。这样一次区间修改最多访问 O(log N) 个节点。关键在于当后续操作需要进入某个带懒标记的节点内部时必须先把懒标记下推给两个孩子否则子节点的 sum 是旧的。下推的时机是“部分覆盖”的那种情况——也就是当前区间没有被查询/修改区间完全包含必须往下走之前先把欠的账还清。提示查询操作同样要先 push 再往下走。很多人更新的时候记得 push查询的时候忘了结果查到一半读到的是没加过懒标记的子节点值整棵树的答案错得悄无声息。4.3 完整实现与注释我把线段树封装成一个结构体build、update、query 都写在里面这样主函数干净也方便赛后直接沉淀成模板。#include bits/stdc.h using namespace std; using ll long long; struct SegTree { int n; vectorll sum, lazy; SegTree(const vectorll a) { n (int)a.size() - 1; sum.assign(n * 4 5, 0); lazy.assign(n * 4 5, 0); build(1, 1, n, a); } void build(int p, int l, int r, const vectorll a) { if (l r) { sum[p] a[l]; return; } int mid (l r) / 2; build(p * 2, l, mid, a); build(p * 2 1, mid 1, r, a); sum[p] sum[p * 2] sum[p * 2 1]; } void apply(int p, int l, int r, ll x) { sum[p] x * (r - l 1); lazy[p] x; } void push(int p, int l, int r) { if (lazy[p] 0 || l r) return; int mid (l r) / 2; apply(p * 2, l, mid, lazy[p]); apply(p * 2 1, mid 1, r, lazy[p]); lazy[p] 0; } void rangeAdd(int p, int l, int r, int ql, int qr, ll x) { if (ql l r qr) { apply(p, l, r, x); return; } push(p, l, r); int mid (l r) / 2; if (ql mid) rangeAdd(p * 2, l, mid, ql, qr, x); if (qr mid) rangeAdd(p * 2 1, mid 1, r, ql, qr, x); sum[p] sum[p * 2] sum[p * 2 1]; } ll rangeSum(int p, int l, int r, int ql, int qr) { if (ql l r qr) return sum[p]; push(p, l, r); int mid (l r) / 2; ll res 0; if (ql mid) res rangeSum(p * 2, l, mid, ql, qr); if (qr mid) res rangeSum(p * 2 1, mid 1, r, ql, qr); return res; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, Q; cin N Q; vectorll a(N 1); for (int i 1; i N; i) cin a[i]; SegTree st(a); while (Q--) { int op; cin op; if (op 1) { int l, r; ll x; cin l r x; st.rangeAdd(1, 1, N, l, r, x); } else { int l, r; cin l r; cout st.rangeSum(1, 1, N, l, r) \n; } } return 0; }建树时从原数组 a 的 1 号下标开始所有查询更新也都用 1-based。这种一致性非常重要因为懒标记和区间下标一旦混用 0-based 和 1-based调试起来会非常痛苦你根本分不清是 push 写错了还是下标写错了。4.4 F 题现场翻车实录我这场 F 题 WA 了三发问题全出在一个地方查询操作没有调用 push。我的 rangeSum 里一开始直接 return sum[p]忘了一件要命的事——当前节点虽然被完整覆盖但如果它身上还背着懒标记而且这个懒标记还没来得及下传那这个节点的 sum 其实已经包含了懒标记的贡献理论上没什么问题。真正的问题是“部分覆盖”的递归分支如果我不先 push子节点的 sum 就没有加上父节点懒标记带来的增量查询结果就会少一块。另外还有两个常见惨案x 是负数时很多人读操作类型用 int 没问题但 x 必须用 long long 读否则负数会爆成奇怪的 int 值其次叶子节点不需要 pushl r 时直接 return避免访问不存在的子节点。5. 常见问题调试实录与对拍技巧5.1 七天七种 WA 速查表症状可能原因解决办法C 题样例过提交错一片sum 或 ans 用 int全部换 long longC 题答案差一点点while 里先移动 l 再减先 sum - A[l]再 lE 题重复数字全部被算成逆序对查询条件写成小于等于只统计严格大于当前值的个数E 题数组越界 REBIT 大小按 N 开大小改为 unique 后排名数 MF 题更新后查询结果偏小查询时没 push 懒标记rangeSum 里先 push 再递归F 题 TLE没关同步或用了 endlios::sync_with_stdio(false); 用 \nF 题段错误线段树数组开小或叶子 push开 4 * N 5push 里判断 l r5.2 我的对拍套路强烈建议各位直接抄写题解这么多年我最大的心得就是树状数组、线段树这种数据结构题想靠肉眼查错基本等于浪费时间直接上对拍。以 C 题为例本地准备一个暴力版本N 只开到 200long long brute 0; for (int l 1; l N; l) { long long s 0; for (int r l; r N; r) { s A[r]; if (s K) brute; } }然后用 mt19937 随机生成小数据分别跑暴力版和双指针版比较输出。只要跑几千组随机数据什么边界 bug、int 溢出、下标错位都会被炸出来。线段树同理可以写一个每次操作都直接 O(N) 扫数组的朴素版来对拍这是性价比最高的 debug 手段没有之一。很多新手不看对拍卡住了就反复盯代码盯到比赛结束也找不出问题。我打 ABC 的经验是超过十五分钟找不到 WA 原因立刻停下写暴力对拍大概率能在一百组随机数据内定位问题。5.3 一些个人习惯这里分享两个我打 ABC 的固定习惯。第一个每道题动笔之前先在草稿纸上写清楚“边界情况”比如区间为空、值相等、左右端点相等、最大数据量下的数值上限。这比先写代码再猜 bug 高效得多。第二个赛后别急着看别人的代码先自己把 F 题的懒标记模板重新默写一遍默不出来就再抄一遍直到形成肌肉记忆。数据结构题在 ABC 里拼的就是手熟模板多敲一次比赛时就能少一次翻车。我把这场 ACEF 的代码整理进自己的模板库之后明显感觉到后面碰类似题目时敲线段树和树状数组的速度快了不少。这大概就是复盘最实在的回报吧。