高开省选 Day 2
Published:
方法论
- 能减就差分
- 不能减就分治
- 二维离线就扫描线
扫描线
P4211 [LNOI2014] LCA🟡
首先差分把询问一拆二。
$dep_{\text{LCA}(i,z)}$ 看成：$i$ 到根的路径 $+1$，查询 $z$ 到根的路径和。
按右端点排序扫描线，做完了。
#637. 【美团杯2021】A. 数据结构
一个元素 $x$ 不出现，当且仅当：
- 所有 $x$ 都在 $[l,r]$ 出现
- 所有 $x-1$ 都不在 $[l,r]$ 出现
这两个性质画在 $l$-$r$ 坐标系上。
TODO:
交换维度
扫描序列，用 DS 维护时间维。
大部分情况是单点询问。
#515. 【UR #19】前进四
TODO:
- 修改：区间 cmin
- 询问：单点被成功 cmin 几次
Segment Tree Beats 可做。
分块
平衡复杂度
分块平衡的经典模型
- $O(1)$ 单点加，$O(\sqrt n)$ 前缀和
- $O(\sqrt n)$ 单点加，$O(1)$ 前缀和
- TODO:
- $O(1)$ 前缀加，$O(\sqrt n)$ 前缀和
- TODO:
P4278 带插入区间K小值🟡
序列，插入，单点修改，查询区间 k 小值。强制在线。 操作数以及值域都在 $7 \times 10^4$ 以内。
需要一个 $O(n \sqrt n)$ 的做法。
首先 $k$ 小有一个经典的不带 $\log$ 做法。值域分块块长 $B$，不用二分答案，而是枚举 $B$ 的倍数。假设最后答案落在 $kB$ 与 $(k+1)B$ 之间，直接枚举就行了。
怎么验证？TODO:
P5611 [Ynoi2013] D2T2🟡
考虑小数据，值域固定 $[1,n]$ 怎么做。$O(n^2)$
分块
TODO:
扩展：一个块有 $n^3$ 个不同答案，分块成 $B = \sqrt[3]{n}$
莫队
回滚莫队，预处理了某些关键点
P8078 [WC2022] 秃子酋长🟡
TODO:
CF1767F Two Subtrees🟡
TODO:
根号重构
P6578 [Ynoi2019] 魔法少女网站
TODO:
杂 Trick
CF1801E Gasoline prices / P13528 [OOI 2023] Gasoline prices / 油价
P3295 [SCOI2016] 萌萌哒 完全强化版。
TODO: