感觉正常 OI 学生很难在不依赖大脑随机性情况下想出这道题,因为我们没有学斯特林公式。
考虑观察操作的影响,并确定还原策略。这道题中我们可以考虑按 \(1\rightarrow n\) 的顺序还原,这样的好处是如果我们每次能保证单次复杂度,那么进入子问题后复杂度同样能得到保证。我们发现每次操作是对区间按奇偶分类,然后再前后分别放入,此外我们能观察到我们不妨令操作区间都为偶数长度区间。我们现在只需要关心待还原的位置,我们希望它往前走,自然能够想到把它放在末尾,将左端点设为目标位置,也就是开头,这样我们的距离就会减少一半,于是此时复杂度 \(\mathcal{O}(n\log n)\)。
提前用操作随机扰动是没用的,因为 \(\log\) 里做减法实在是太逊了。
实在没办法考虑倒着做,尽量不要硬想,这种题基本上不会复杂到哪去。我们倒着做一次操作时区间前一半和后一半取出来然后镶嵌插入。此时发现我们还是可以从前往后还原,不过这样更劣了,我们甚至还得关心 \(2i\) 是否大于 \(n\),且我们仍然没能优化复杂度,我们还是不能动之前操作过的东西,导致我们的复杂度还是 \(\sum\log (i-j)\) 的状物。
我们发现这个减法在期望下最后求和就是 \(n\log n\),我们有没有什么厉害的办法可以优化掉一些东西,比如说不能操作之前的东西就很鸡肋。我们发现我们希望操作的是一段前缀,那么我们考虑倒着还原不就不会遇到这种问题了吗?我们倒着还原,对于当前位置 \(i\) 我们希望把它放到 \(n\),我们操作 \([1,2i]\) 可以让 \(i\) 倍增,如果 \(2i>n\) 直接操作 \([2i-n+1,n]\) 即可一步归位。斯特林公式可以证明,\(\sum \log (\frac i j)\) 是线性的,于是配合上一点随机扰动我们就做完了。
太困难!