[Ynoi2000] pri

· · 题解

问题等价于区间翻转区间顺序对数，显然没有复杂度比较好的做法。

将操作序列每 B 个分一组，对每组进行处理。

将值域按 $C$ 大小分块。考虑如下三类贡献： - 每段内部的顺序对 $(i,j)$ 数。 - 属于同一个值域块、不属于同一个段的 $(i,j)$。 - 不属于同一个值域块、不属于同一个段的 $(i,j)$。 对于第一类，预处理 $O(n\log n)$ 求出每个连续段内部的顺序对数。 对于第二类，只有 $O(nC)$ 个 $(i,j)$，预处理这些 $(i,j)$ 属于哪两个块。 接下来考虑对操作序列进行分治，并建立分治结构。 分治到一个操作序列区间 $q_l,\cdots,q_r$ 时，有若干个等价类会合并，只会有 $O(len)$ 个等价类。 对于当前分治区间，设当前区间长度为 $k$，要维护的信息是： - 每个等价类内部的顺序对个数。（$O(k)$ 个信息） - 每个等价类中，在每个值域块中的数个数。（$O(k\frac{n}{C})$ 个信息） - 对于上面的第二类的 $O(nC)$ 个 $(i,j)$，记录这些 $(i,j)$ 属于哪两个块，记录每两个块间的 $(i,j)$ 个数。（$O(k^2)$ 个信息） 类似 [TB5x](https://www.luogu.com.cn/problem/P7723)，从最少的等价类开始，依次构造出每个区间的等价类，即从分治的叶子节点开始构造。 每个操作对于坐标的修改是一个由两个连续段构成的排列，第一段进行了翻转。 而由 $x$ 个连续段构成的排列复合一个由 $y$ 个连续段构成的排列最多得到 $x+y$ 段。 先进行分治建树，每次合并时，通过左右儿子区间的排列求出当前点的排列，同时可以求出当前排列的每一段（即每个等价类）对应了左右儿子的哪个等价类，以及当前的每一段是否被翻转。这部分复杂度 $O(B\log B)$。 然后从上到下分治，每次从 $q_l,\cdots,q_r$ 移动到 $q_l,\cdots,q_{mid}$ 和 $q_{mid+1},\cdots,q_r$，会发生等价类的合并。此时可以计算贡献，来维护上面的三类信息。由于已经得到了等价类的对应关系，这部分是容易的： - 对于原来的三类信息，可以直接累加。 - “每个等价类内部的顺序对个数”会增加，但由于只要考虑不属于同一个值域块、不属于同一个段的 $(i,j)$，只需要对 $O(k\frac{n}{C})$ 的信息做前缀和，就可以计算。 分治到叶子节点时，取第一个区间的内部的顺序对个数信息，就得到了答案。 复杂度 $T(k) = 2T(\frac{k}{2}) + O(k^2+k\frac{n}{C})$，于是处理一块的复杂度为 $O(B^2 + B\log B\frac{n}{C})$。 加上之前的 $nC$，总复杂度 $O(\frac{m}{B}(nC + B^2 + B\log B\frac{n}{C}))$。 取 $B=n^{2/3}\log^{1/3} n,C=n^{1/3}\log^{2/3} n$ 得到最优复杂度 $O(mn^{2/3}\log^{1/3} n)$。