[Ynoi2000] pri

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

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

\(B\) 个操作会将序列划分为 \(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，从最少的等价类开始，依次构造出每个区间的等价类，即从分治的叶子节点开始构造。

每个操作对于坐标的修改是一个由两个连续段构成的排列，第一段进行了翻转。

而由 \(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)\)。