题解：P11721 [清华集训 2014] 玄学

· · 题解

这题复杂度是一个 \log，不是两个。复杂度水的方法过题就不要降难度标签了。

做法

对操作序列构建一个线段树 T，下标为操作时刻。

对于线段树上每个节点 T[l,r] 分别维护：按顺序应用这个节点所有操作后，n 个位置耳机玄学值分别受到的总变换（形如 \times a+b \pmod m）。可以发现 n 个位置总变换的序列只有 O(操作次数) 段不同的值，也就是 O(\min(n,r-l))。因此，维护只需要记录这个连续段分界点的有序数组，查询时在数组上二分。

查询只需要找到对应操作区间的 O(\log q) 个线段树节点，然后逐个查询线段树节点所有操作对询问的耳机位置的作用计算即可。

由于本题操作是在线地逐个向后增加的，线段树也需要动态构建，具体来说就是每增加一个操作就创建出所有以该操作为右端点的线段节点。大体上不影响时空复杂度。

如果朴素地计算，时间复杂度为 O(q\log n\log q)。

时间瓶颈为每次查询要在 O(\log q) 个节点上二分，可以使用类似分散层叠的算法优化。具体如下：

  1. 线段树上每个节点的分界点序列是两个儿子的分界点序列的有序归并。在线段树节点上记录每个分界点在两个儿子的分界点序列上各自对应的位置。每次查询只需要在线段树根节点二分一次。（此技巧被称为“归并树”）
  2. 动态构建线段树过程中会有多个线段树根，需要单独讨论。假设这些线段树（二进制分组）的分界点序列分别是 A_1,A_2,\dots A_k，大小分别是 a_1\gt a_2\gt \dots \gt a_k，采用分散层叠的方法，对于 i=1,2,\dots ,k 依次从 A_i 中等分取 a_{i+1} 个放进 A_{i+1} 归并出新的 A_{i+1}，长度最多增加一倍。这样，查询时二分出 A_{i+1} 的排名结果后可以知道在 A_{i} 中处于相邻的哪两个等分点之间，再在 A_i 中二分的时间复杂度是 O(\log \frac{a_{i}}{a_{i+1}})。因此 k 次二分的总时间复杂度是 O(\log \frac{a_{1}}{a_{2}}+\log \frac{a_{2}}{a_{3}}+\dots )=O(\log a_1 +k)=O(\log n+\log q)。
  3. 按照上述分析，动态构建线段树的时间复杂度仍为线段树节点大小总和的线性（分界点序列类似归并排序可以线性合并，分散层叠每次也只要重构最后一个）。

综上，总时间复杂度为 O(n+q(\log n+\log q))。

原题题解是同复杂度的可持久化平衡树做法。见：https://qoj.ac/download.php?type=solution&id=16