Rainboy 个人题单

一、线段树

本章的学习路线：主线是 P3372 → aalc001_c → 19D → P4116；U420425 与 U502676 是插在中间的补充题，可以先过主线，卡在“下降”上时再回来刷这两道。

flowchart TD
  P3372["线段树单点改/区间查<br/>P3372 或已会"]
  aalc001c["AT aalc001_c<br/>只练「下降」这 15 行"]
  CF19D["CF19D Points<br/>二维 + max 聚合 + 找最小坐标"]
  P4116["P4116 Qtree3<br/>把 (x,y) 换成 (dfn, rdfn)，min 代替 max"]
  U420425["U420425 线段树二分 2<br/>懒标记 + 按和下降"]
  U502676["U502676 线段树上二分模版<br/>维护 max + 找第一个大于 k"]

  P3372 --> aalc001c
  aalc001c --> CF19D
  CF19D --> P4116

  P3372 -.-> U420425
  U420425 -.-> U502676
  U502676 -.-> aalc001c

• luogu P3372 【模板】线段树 1题解
  训练点：懒标记下传时机，左右区间边界，long long 防溢出。
• luogu U420425 线段树二分 2题解
  训练点：区间和够不够用「还差多少」表示；树上下降依赖元素非负带来的单调性。
• luogu U502676 线段树上二分模版题解
  训练点：把聚合量从区间和换成区间最大值；判据从「够不够」换成「这段最大值是否大于 k」，mx <= k 就整段剪掉。
• atcoder aalc001_c Binary Search on a Segment Tree题解
  训练点：带着余量 rem 下降；向右找最小 $r$、向左找最大 $l$ 两个方向的对称写法；无解用哨兵位置吸收。
• codeforces 19D Points题解
  训练点：外层按 $x$ 维护区间最大 $y$；mx <= limit 剪枝定位最左 $x$；组内用 std::set 或压缩后的 Fenwick 找大于 $y$ 的最小值。
• luogu P4116 Qtree3题解
  训练点：双 dfs 序把祖先关系化成二维偏序；结点维护 min 后找第一个 rdfn <= Y 的位置；对照重链剖分 + 每条链 set 的 $O(\log^2 n)$ 写法，理解两种做法的取舍。

二、序列与路径上的「先买后卖」

本章的学习路线：先在一维上把观察练熟（LeetCode 121 是已经会的那一版），再依次换容器——把「整个数组」换成「任意询问区间」（ROJ 1820），把「数组」换成「图上的一条有向路径」（abc188_e），最后把「一条路径」换成「树上路径 + 整段加价」（P3976）。每换一次容器，摘要就要多带一点东西：区间版要可合并，DAG 版要拓扑序，树版要能反着用并支持懒标记。

flowchart TD
  L121["LeetCode 121<br/>整个数组一次扫描，维护此前最低价"]
  R1820["ROJ 1820 区间最大利润<br/>任意询问区间，摘要 (min, max, best)"]
  A188E["AT abc188_e Peddler<br/>数组换成 DAG，按编号做拓扑序"]
  P3976["P3976 旅游<br/>树上路径 + 路径加价 + 反向段"]

  L121 --> R1820
  L121 --> A188E
  R1820 --> P3976
  A188E --> P3976

• roj 1820 区间最大利润题解
  训练点：把「历史最低价」压成可合并摘要 $(min, max, best)$，合并时必须带上跨段项 $max_R - min_L$；再对照倍增写法，理解「合并满足结合律」才是能上树的前提。
• atcoder abc188_e Peddler题解
  训练点：$X_i < Y_i$ 保证编号就是拓扑序，一次扫描维护「能走到 $v$ 的最低买价」；注意答案允许为负，0 不能当初始化兜底。
• luogu P3976 [TJOI2015] 旅游题解
  训练点：路径拆成 $O(\log n)$ 段 dfn 区间后，$a$ 侧的 dfn 增序与旅行方向相反，所以摘要要带 bwd、查询要 flip；整段加价只平移最值，正好用懒标记。

三、扫描线与差分

y 方向上要的是「区间加、单点查」，所以这一章的前置是差分 + 树状数组；真正的新东西是把每个矩形拆成「进入 / 离开」两个事件，按 $x$ 排序后扫过去。

• roj 1416 矩形覆盖计数题解
  训练点：矩形拆成 $x=l$ 加、$x=r$ 减两个事件；同一个 $x$ 上先做事件再回答询问，半开区间的边界处理被顺序自动吸收；坐标到 $10^9$ 先离线离散化再开树状数组。