P3242 [HNOI2015] 接水果 抽象做法

好吧好吧，自己做出来的第一道整体二分。

省流：理解能力比较强的话直接拖到最后看算法流程吧。

下面我们称输入时盘子的权值为“盘子的大小”，与文中使用的算法给盘子的赋权区分开。

一堆询问第 \(k_i\) 小，考虑整体二分。

先考虑外部过程。

上整体二分板子，每次二分 \(mid\)，形象地把盘子集合掰成两半，左集合里的盘子满足大小都 \(\leq mid\)，右集合就是剩下一半。

接下来只考虑左集合的盘子，计算出对于水果集合中第 \(i\) 个水果包含了多少个左集合中的盘子，记为 \(c_i\)。把 \(c_i\leq k_i\) 的那一部分水果随着左集合向左侧二分 \([l,mid]\)，剩下的水果 \(k_i\gets k_i-c_i\) 排除掉左集合贡献之后，再随着右集合向右侧二分 \([mid+1,r]\) 即可。

当 \(l=r\) 时，直接给水果集合里的水果答案就行。

真正麻烦的其实是怎么能快速算出来每个水果包含了多少个左集合中的盘子。

考虑找出一条路径 \(u'\leftrightarrow v'\) 是母路径 \(u\leftrightarrow v\) 的子路径的充要条件，可以发现当且仅当 \(u'\) 和 \(v'\) 都在 \(u\leftrightarrow v\) 上，\(u'\leftrightarrow v'\) 才构成 \(u\leftrightarrow v\) 的子路径。那么想数出子路径数量，就是想数有多少条路径两个端点都同时在母路径上。这种两个同时存在做贡献只存在一个或者不存在都不做贡献的形式，容易想到做异或哈希。

然而你发现这很难异或哈希，因为异或哈希不能维护满足条件的路径数量，但是这启发我们使用异或并尝试使得位与位间不冲突以维护子路径数量。

我们不妨给所有盘子一个互不相同的编号 \(i\)，权值设置为 \(2^i\) 并把权值挂在两个端点上，这样我们可以查询水果 \(u\leftrightarrow v\) 这一路上的权值异或和，而它的 popcount 就是水果 \(u\leftrightarrow v\) 里有多少个盘子的恰好一个端点。再做一次补集转化，用 \(u\leftrightarrow v\) 里盘子端点的总数减掉这个 popcount 再除以 \(2\)，就是水果 \(u\leftrightarrow v\) 里两个端点同时都在的盘子数量。

为了降低时间复杂度，编号可以直接依次给成 \(0\sim p-1\)，然后开 \(n\) 个大小为 \(p\) 的 bitset，这样每次对权值的操作（异或或者查 popcount，以及实现过程中需要做的清空等）就都是 \(\mathcal O(1)\) 或者 \(\mathcal O(\frac{p}{w})\) 的了。

现在问题转化成，每次只有左集合的那一部分盘子是有效的，怎么求一条路径上的异或和。为了保证复杂度，我们不能每一次都扫一遍整棵树，但是我们发现只有左集合盘子的端点的权值是有用的，这启发我们每一次都把左集合盘子的端点当做关键点建立虚树，建立虚树的复杂度和虚树上的节点数量都是左集合大小级别的，复杂度没有问题。

为了让虚树总是树从而方便操作，可以把根节点当做权值为 \(0\) 的关键点也加进虚树，无伤大雅。

建立虚树之后事情就简单多了，对虚树垒一波树上异或前缀和，然后把查询的水果 \(u\leftrightarrow v\) 路径的端点 \(u,v\) 等价地挪移到虚树节点上，然后直接类似树上差分，把四个 bitset 异或在一起就是水果 \(u\leftrightarrow v\) 路径在只有左集合盘子的情况下的权值异或和。

这里挪移端点是因为水果 \(u\leftrightarrow v\) 的端点 \(u,v\) 并不一定都在虚树上，但是我们只有虚树上的点是有信息的，所以我们要收缩这条路径为它的一个子路径，这条子路径需要满足两端都是虚树节点，且没有损失任何信息（在收缩过程中没有丢掉任何一个关键的虚树节点）。换句话说，这个收缩的过程就像是把左右端点分别向路径中间收缩，直到各自都收缩到一个虚树节点。这样我们原来想查的 \(u\leftrightarrow v\) 权值异或和，就可以转化成查这两个虚树节点在虚树上的路径的异或和，而这是一个简单的虚树上的树上差分。

挪移端点需要进行分类讨论，还要查询树上一段路径上有没有关键点。鉴于我们计算每个水果的总答案时还要查询一条路径上关键点的数量，但是我们每次都只需要设置一些点是关键点，使用树上差分加树状数组可以较快地解决。

有点麻烦，梳理一下算法流程：

1. 按照输入顺序，给输入的第 \(i\) 个盘子权值 \(2^{i-1}\)。
2. 整体二分，以 \(\leq mid\) 为盘子大小的分界线，得到盘子的左集合。
3. 将左集合盘子的路径端点设置为关键点，建立虚树，然后把左集合盘子的权值挂到路径端点上。
4. 对虚树垒权值的异或前缀和。
5. 考虑水果，对于水果 \(u\leftrightarrow v\)，把两个端点等价收缩到虚树上。
6. 查询收缩后的两端点在虚树上的路径权值异或和，可以通过树上差分得到，显然这个等价于在只有左盘子集合的情况下原 \(u\leftrightarrow v\) 的路径权值异或和。
7. 查到这个东西，再查一个 \(u\leftrightarrow v\) 路径上关键点的数量，就可以算出来这个水果包含了多少个左盘子集合里的盘子。以此再划分水果，整体二分递归下去就可以了。

对于每一次判定，建立虚树复杂度 \(\mathcal O(n'\log n)\)，给虚树垒前缀异或和复杂度 \(\mathcal O(\frac{n'p}{w})\)，对于每个水果计算包含盘子数量复杂度 \(\mathcal O(n' \log n+\frac{n'p}{w})\)。给盘子大小做离散化之后，整体的复杂度就应该是 \(\mathcal O(n\log^2 n+\frac{np}{w}\log n)\) 的。

这玩意算出来倒不是很抽象，但是常数很大。然而并不妨碍开了 O2 之后 bitset 快得飞起，可以在 3s 内通过，不开 O2 无法通过。总时间来说比 SA 又 assert 又不开 O2 的 \(\mathcal O(n\log ^2 n)\) 跑得快八秒（

实现的时候细节很多，要特判各种 LCA 是根节点的情况，还要写一堆板子，还有清空（清空虚树和树状数组）。但是最后想清楚了写出来还是觉得蛮清晰的。我大概调了两个小时。

代码写了 7.3K，太长了就放这里吧。

AC Record。