菜王的 blog

给一个虽然没有那么优秀但是比较好想的 $O(2^{1.5n} + 2^{0.5n}q)$ 做法。

首先，可以观察到交换操作的顺序是对操作后的序列没有影响的，而对于任意一个 $k$ 交换操作执行两次就会抵消，所以一个长度为 $2^l$ 的序列经过若干次交换操作后至多能形成 $2^l$ 种不同的序列。

然后我们把序列分块，块长为 $2^{\lfloor0.5n\rfloor}$。考虑根号分治的思想，如果一次操作的 $k \ge \lfloor0.5n\rfloor$，那么我们可以直接 $O(2^{0.5n})$ 大力交换块；否则，发现所有 $k < \lfloor0.5n\rfloor$ 的交换操作对于每一块的影响是相同的，我们只需要简单的记录一个 $\lfloor0.5n\rfloor$ 位二进制数 $sta$，$sta$ 的第 $i$ 位表示每一块的 $k$ 为 $i$ 的操作是否生效，每次将 $sta$ 的第 $k$ 位反转即可，这样就做到了 $O(2^{0.5n})$ 单次修改。

考虑求答案。我们在询问之前，对于每一块的所有可能的状态，预处理出一个结构体 $b_{i, j}$，记录第 $i$ 块交换操作的状态为 $j$ 时的区间和，最大前 / 后缀和，最大子段和，时间复杂度为 $O(2^{1.5n})$。操作完毕后，直接把所有的 $b_{i, sta}$ 按顺序合并即可做到 $O(2^{0.5n})$ 单次查询。

总体来讲，大概思路就是：块间暴力，块内预处理。

具体细节可以看代码实现，有详细的注释。