DS trick

· · 个人记录

摆

按 lxl 讲课的顺序来。

写了的题我打个 \color{green}\surd 。

倍增值域分块

引入：CF702F \color{green}\surd

按 q 为第一关键字、c 为第二关键字排序后，这相当于对于维护若干个二元组 (a_i, b_i)， a_{i}\ge q 的二元组 a_{i}-q, b_{i}+c。

对于 [0, q) 和 [2q, \infty) 的部分，操作后其并集的 a_{i} 相对大小不会变。FHQ 分裂后直接打 tag 即可。对于 [q, 2q] 的部分暴力减，重新放入平衡树内，暴力部分每次操作后值会减半，所以总复杂度 O(n\log V \log n)。

这种本质上是对被减的数分类，减半部分花费至多次 \log 的暴力，大于部分的能够整体 tag。

上面这个做法并不能很好地应对区间操作，这是为什么？因为我们每次分出的值域块是动态的，我们需要一个套路化的做法。

将值域分为 [2^{k}, 2^{k+1}) 的 \log v 个块 S_{k}，对于 2^{k+1}\le x，S_{k} 中的元素不被影响，对于剩下的每个块 S_{k}，若 S_{k} 存在元素 -x 后不再属于 k，则直接暴力找出这些元素，丢到对应的块，一个点发生掉落的次数的上界是块的数量，丢完之后打 tag 即可。

P7447 [Ynoi2007] rgxsxrs

直接套用上面的做法，听说好像要卡点常。

CF1515I \color{green}\surd

T-shirt 动态版。

对重量值域分块，对于当前 c 所在块 [2^k, 2^{k+1})，考虑 c 的掉落是谁造成的，如果是一个 \ge 2^{k} 的物品 i，则需要满足 \forall v_{j}>v_{i}, w_{i}f(i, c)+\sum a_{j}w_{j}\le c，随后 c 掉落，亦或是选了足够多个 <2^{k} 的物品，使得总和超过 \frac{c}{2}。

对于第一种情况，线段树上维护区间内 a_{i}-sumb_{[l, i)} 的 \max 和 sumb 可以解决（注意不是维护 [1, i) 而是 [l, i)，因为后面会有对左端点的限制）。

对于第二种情况，注意到选的东西本质上是一个（下标的）前缀区间 [1, r) 和 r 的部分，r 物品以后也不会选，因此直接把线段树每次询问左端点变成 r+1（这就是上面线段树不直接维护从 1 开始的前缀的原因）。

P4587 [FJOI2016]神秘数 \color{green}\surd

求区间子集和的 \operatorname{mex}。

先按值从小到大排序，暴力怎么做？加边加边然后并查集查询令当前可表示区间为 [0, x]，考虑剩余没有用到的最小的元素 k，若 k\le x+1 则区间变为 [0, x+k]，否则 x+1 就是答案。

更进一步的，我们可以把 [0, x+1] 中未选过的数全部选上，考虑下一次操作，[0, x+k] 中 [0, x+1] 中的数全都被选，那么下次加的数必然 \ge x，也就是说两次加必然使得值域翻倍，维护选了的最大数 m，主席树查区间 [l, r] 中 [m, x+1] 内数的和即可。

带单点修改怎么办？\color{green}\surd

值域翻倍？考虑用上面的值域分块做法，只要块内有一个被选，那么一定能选整个块，做完了！

类似的还有 P9069 loj3527

减半警报器

引入 Gym104065B

题意简化：有 n 个灯，当 [l_i, r_i] 中有 k_i 个灯被点亮时 i 号灯随后被点亮，查询最终状态亮灯个数。

利用一个简单的思路：我们将单个询问区间拆分为 A[l, mid], B(mid, r] 那么两个区间的其中一个亮灯数量至少大于等于 \frac{k_i}{2} 才亮。我们考虑类似于线段树的结点分配方式将询问区间分为两段 A, B，并分配“负重”\frac{k_i}{2}，某一时刻如果 A/B 中有一个“负重”为 0 则将这两个区间拿出来，将“已删除负重”清零后重新分配即可。那么由上得知负重每次必减半。

对于所有询问，我们需要考虑修改操作的简便，所以我们利用线段树把每一个询问区间拆分成 \log n 个承重区间，分配负重是一样的。

维护时只需要在线段树一条链（单点修改）的每个结点上进行一个前缀/后缀加以及取 \min 即可。

更有效率的方法是 KDT 直接暴力均摊 O(n\sqrt{n})，常数更小。

支配对

一般都是求 \min/\max f(i, j|i, j \in[l, r]) 这类的东西，我们只找那些真正会参与比较的匹配对（称为支配对），一般通过启发式合并/分治来约束支配对个数。

树上区间最近点对

最早应该是在 gym104076L，lxl 把它丢到了 lg 上（P9058\color{green}\surd ）。

考虑点分治，考虑以分治中心 rt 为 \operatorname{LCA} 的点对，有效的支配对应满足 \max(dis_l, dis_r)\le \min_{i\in(l, r)} dis_{i}，否则将 l, r 其中一个移到内部最小值处必然更优。

将点按编号排序，枚举右端点 i，考虑一个 x 能作为左端点，应满足它是一个 [x, i] 的最小值，所以单调栈维护 x，每次右端点有效为 i 的有效支配对位 (stack.top, i)，反过来维护 i 是左端点的情况，不需要考虑是否在同一个子树的情况，因为到下一层会更优。

对于所有支配对 (x, y, \operatorname{dist}(x, y)) 和询问 [l, r]，考虑扫描线扫 r, y，树状数组更新后缀最小值即可。时间复杂度 O(n\log^2 n)，空间复杂度 O(n\log n)。

P7880 [Ynoi2006] rldcot \color{green}\surd

类似地，求一个点 x 不同子树内产生的有效支配对，考虑启发式合并的过程，每次暴力枚举小的子树内的每一个点 x，找其大的块内的前驱和后继 l, r，(l, x) 和 (x, r) 是有效的，产生的支配对数量即启发式合并复杂度。

对于询问，相当于求 [l, r] 覆盖的支配对的颜色种数，扫描线一下就好了。

区间最近点对（一维）

CF765F/P5926/CF1793F\color{green}\surd

You're wrong, here's why

严格弱于树上版本

将一个数视为点，相邻两数之间连边权为差的绝对值的边，i 向 a_{i} 连边，归约到树上区间最近点对

区间最近点对（二维 欧几里得距离）

P9062