P8381

gyc18 · 2022-05-05 12:33:41 · 题解

此题解为官方题解

爆搜打表可以发现：能够取某一个 x 归位的排列必须满足逆序对数为偶数。同时取 x\leq n/2 的时候都可以归位所有逆序对数为偶数的排列。

有如下做法：

取一个偶数为 x。

Step 1：将 [1,n-2x-1] 以内的元素归位。

这一步非常简单，对于一个元素 x，当它旁边空余元素很多的时候，可以：

• 用 1 次操作移动 x-1 个元素到它的右边；
• 用 2 次操作移动 2 个元素到它的右边。（注意这个在一开始的几个左边不够用的时候要用右边的作为中转来输送 2 个元素）

由于 x-1 是奇数，所以这样足以凑出所有 \geq x-1 的数，且每个数都只需要 O(n/x) 次操作。这一步复杂度为 O(n^2/x+nx)。

Step 2：将剩下的元素归位。

等价于用 x 排序长度为 2x+1 的排列。

首先我们构造一种操作将第一个元素向后移两位：

反过来就是把第一个元素向左移两位。

那么我们先不断右移 [1,x+1] 把 2x 转到第一位，然后把 2x 右移 2 位，再把 2x 转到第一位（这只需要 4 次），再右移 2 位……如此循环。如果最后 2x 和 2x+1 正好相邻，那么 2x 归位；否则把中间那个左移两位，也能使 2x 归位。

然后依次递减处理就可以了。容易证明这个做法在有偶数个逆序对的时候是对的。

由于我们可以线性次操作复位一个元素，所以构造量级是 O(x^2)。

总构造量级是 O\left(\dfrac{n^2}{x}+nx+x^2\right)。取 x=O(\sqrt n) 得到最低构造量级 O(n\sqrt{n})。

这样直接实现的常数比较大，对第一部分有一种比较有效的剪枝：到最后小步输送元素的时候，如果发现到某一个时刻右边恰好剩 x 个，那么直接给左边挂点东西然后推过去，可以省去 x-1 次操作。加上就可以过了。

数据随机是因为这玩意我没法卡，直接逆序跑的比随机次数还少，逆序小范围随机打乱也卡不住，，，