自动搬运

查看原文

来自洛谷，原作者为

	mrsrz 故障机器人

搬运于2025-08-24 22:09:24，当前版本为作者最后更新于2019-04-23 13:57:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑某一时刻数列的状态，一定是前面一段有序，后面一段无序。

首先考虑第三个操作，显然用一个变量记一下全局异或的值$X$就可以了。对于第一个操作，先把$x$异或上$X$再插入。

计算贡献的话，可以按位考虑，记录一下这一位有多少个即可。

如果没有排序操作，直接记一下每一位的前缀和即可。

考虑排序操作，前面有序的我们不去动它，后面无序的，直接把它插在正确的位置即可。显然一个数只会被插入一次。用01Trie或线段树维护一下区间各个位的出现次数即可做到区间查询（可以用前缀相减来搞）。

然而操作3会改变已经排完序的数的大小关系。我们考虑一下性质。

考虑最高位，如果它异或上了1，则这个序列的后一部分（最高位为1的那些数）会整体变到前面来。而每个部分内部的相对顺序不变。然后对每一部分，再对次高位考虑。依次类推。

对应到数据结构内部，我们发现，如果某一位异或上了1，相当于这一层的节点的左右儿子交换了一下。

我们不需要真的交换，只需要在询问的时候判断一下往哪边走即可。

这样就非常简单了，代码也很好写。

时间复杂度$O(n\log^2 A)$。