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]$ 内数的和即可。

[带单点修改怎么办](https://www.jisuanke.com/problem/A2285)？$\color{green}\surd $

值域翻倍？对于上面的值域分块做法，只要块内有一个被选，那么一定能选整个块，[做完了](https://www.cnblogs.com/sizeof127/p/17236276.html)！

类似的还有 P9069 loj3527

## 减半警报器

## 支配对

一般都是求 $\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~~](https://codeforces.com/blog/entry/112709)

严格弱于树上版本

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

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

P9062

正在渲染内容...