Strange Permutation 题解

思路

把每个长度至少为二的翻转区间看作一个块，未被翻转的位置看作长度为一的块。因为区间互不相交，一次操作与把位置序列唯一划分成若干块等价：长度为 $L$ 的块倒序输出原排列的这一段，并消耗 $L-1$ 的代价。不同块划分作用在排列上会得到不同结果。

设 $F[x][r]$ 表示从位置 $x$ 开始、还可使用至多 $r$ 代价时的不同结果数，超过 $4\times10^{18}$ 的数统一截断。边界 $F[n+1][r]=1$，转移为

其中只枚举没有越过 $n$ 的块。暴力层直接枚举所有块划分并排序；中间层对每次询问从左到右选择块，复杂度 $O(nq)$。

做法

满分算法注意到，在状态 $(x,r)$ 选择长度 $L$ 的块后，当前输出的第一个数是 $p_{x+L-1}$。这些数互不相同，因此把至多五个候选块按该值排序，其子树在字典序中恰好连续，子树大小就是对应的 $F[x+L][r-L+1]$。

真正需要加速的是连续选择长度一的块。设在状态 $(x,r)$ 中，排在长度一块之前的方案总数为 $b_x$。若当前名次 $j$ 满足

就选择长度一块并令 $j\leftarrow j-b_x$。一段连续长度一转移可以用三元组 $(lo,hi,sub)$ 描述：初始名次位于 $(lo,hi]$ 时整段都可跳过，跳过后减去 $sub$。两段拼接时将后一段的区间整体加上前段的 $sub$，再求交即可。对每个剩余代价建立倍增表。

回答询问时，用倍增跳过目标位置之前尽可能长的长度一段；一旦选择了长块，若目标位置落在块内可立即按倒序映射回答，否则消耗代价后继续。长块至多出现四次，所以单次询问复杂度 $O(c\log n)$。

复杂度

总复杂度为 $O(cn\log n+cq\log n)$，空间复杂度为 $O(cn\log n)$，其中 $c\le4$。