题解：P7708 「Wdsr-2.7」八云蓝自动机 Ⅰ

· · 题解

选自窝的莫队学习笔记。

八云蓝自动机 Ⅰ

首先我们对于操作 1 转换，我们给 k 单独再开一个点 a_c，这样我们就可以把操作 1 转换成操作 2 了。

对于区间问题，我们考虑使用莫队进行维护。

我们记录当前 a 的值，pos_i 表示原来第 i 个位置的数现在在哪里，rev_i 维护现在第 i 个数原来在哪里，和 add_i 现在第 i 个位置上查询了多少次。

首先我们先考虑指针 r 往右移的情况。

  1. 这个操作是交换

直接交换 a_x 和 a_y，rev_x 和 rev_y，pos_{rev_x} 和 pos_{rev_y}。

  1. 这个操作是查询

直接给 ans 加上 a_x，然后 add_x 加 1 即可。

然后我们考虑指针 l 往左移的情况。

  1. 这个操作是交换

我们同样先交换 a_x 与 a_y，rev_{pos_x} 和 rev_{pos_y} 以及 pos_x 和 pos_y。

由于这个操作会影响到后面的查询操作，所以这个操作会改变答案。所以在交换后我们需要加上 (a_{pos_x} - a_{pos_y}) \times (add_{pos_x} - add_{pos_y})。

  1. 这个操作是查询

和上面一样，ans 加上 a_{pos_x}，add_x 加上 1。

剩下两种类似，只需改改符号即可。时间复杂度 O(n\sqrt n)。

最后要注意本题对 2^{32} 取模。

code