Luogu5312 [Ynoi2011] 竞赛实验班

发表于 更新于 分类于 ， ， 阅读次数：

题意 : 给出长为 的数组 ，支持下列操作 ：

  1. 在数组 的末尾添加一个数 。
  2. 区间求和。
  3. 将数组 中的每个数 都改为 。（ 表示异或操作）。
  4. 将数组 从小到大排序。

，时限 ，空限 。

若不存在操作 3，序列肯定形如一段排好序的以及一段未排序的，而且排好序的段只会延长。

对于排好序的数，用权值线段树维护，区间求和可以转化为前 小求和。

对于未排序的部分，直接用树状数组维护。

接下来考虑操作 3。

记下两类标记，一类是全局异或标记 ，一类是排序段排序时的异或标记 。

当 push_back 一个数 时，要将其异或 。

用 01Trie 维护排好序的部分，查询前 小时根据 将行走的方向取反。

我们要支持查询子树在异或 后的和，于是要维护每一位的 的个数。为了节省空间，只有一个儿子的点的信息可以引用儿子的信息。即压缩 Trie。

对于未排序的部分，用前缀和维护即可。

在全局排序时，只需将未排序的部分插入 Trie 中。

时间复杂度 ，空间复杂度 。