1645. 普通平衡树

您需要写一种数据结构(可参考题目标题),来维护一些整数,其中需要提供以下操作:

  1. 插入一个整数 x。
  2. 删除一个整数 x(若有多个相同的数,只删除一个)。
  3. 查询整数 x 的排名(排名定义为比当前数小的数的个数 +1)。
  4. 查询排名为 x 的数(如果不存在,则认为是排名小于 x 的最大数。保证 x 不会超过当前数据结构中数的总数)。
  5. x 的前驱(前驱定义为小于 x,且最大的数)。
  6. x 的后继(后继定义为大于 x,且最小的数)。

本题强制在线,保证所有操作合法(操作 2 保证存在至少一个 x,操作 4,5,6 保证存在答案)。

输入

第一行两个正整数 n,m,表示初始数的个数和操作的个数。

第二行 n 个整数 a_1,a_2,\cdots,a_n,表示初始的数

接下来 m 行,每行有两个整数 optx',opt 表示操作的序号(1\le opt\le 6),x 表示加密后的操作数。

我们记 last 表示上一次 3,4,5,6 操作的答案,则每次操作的 x 都要异或上 last 才是真实的 x。初始 last 为 0。

输出

输出一行一个整数,表示所有 3,4,5,6 操作的答案的异或和

样例

标准输入 复制文本
6 7
1 1 4 5 1 4
2 1
1 9
4 1
5 8
3 13
6 7
1 4
标准输出 复制文本
6

提示

样例加密前为:

6 7 1 1 4 5 1 4 2 1 1 9 4 1 5 9 3 8 6 1 1 0

原题为 洛谷P6136 ,本 OJ 处数据可能弱于原题,如果你想确保你的代码复杂度足以过题,建议在通过本题后在洛谷上交一下题

登录以提交代码。
单点时限 3 秒
内存限制 88 MB
提交 39
通过 13