题解 P5312 【[Ynoi2012]D2T1】

· · 题解

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

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

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

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

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

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

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

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

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

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

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