问题等价于区间翻转区间顺序对数,显然没有复杂度比较好的做法。
将操作序列每 \(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)\)。
标签:Ynoi2000,frac,log,复杂度,分治,pri,等价,每个 From: https://www.cnblogs.com/Rainbowsjy/p/17983663