P6136 【模板】普通平衡树(数据加强版)
题目描述
你需要动态地维护一个可重集合 M,并支持以下六种操作:
1.向 M 中插入一个数 x;
2.从 M 中删除一个数 x。若 M 中有多个 x,只删除其中一个;
3.查询 M 中有多少个数比 x 小,并将得到的答案加一;
4.将 M 中的数从小到大排列,查询排名第 x 位的数;
5.查询 M 中 x 的前驱,前驱定义为小于 x 且最大的数;
6.查询 M 中 x 的后继,后继定义为大于 x 且最小的数。
本题强制在线:每次操作的真实操作数 x 需要由输入给出的加密值解密得到。保证所有操作合法,即操作 2 时 M 中至少存在一个 x,操作 4 时存在排名第 x 位的数,操作 5,6 时分别存在 x 的前驱和后继。
输入格式
第一行输入两个整数 $n, m \left(1 \leqq n \leqq 10^5;\ 1 \leqq m \leqq 10^6\right)$ 代表初始数的个数与操作次数。
第二行输入 n 个整数 $a_1, a_2, \dots, a_n \left(0 \leqq a_i < 2^{30}\right)$ 代表初始时 M 中的数。
此后 m 行,第 i 行输入两个整数 $\mathrm{opt}_i, x'_i \left(1 \leqq \mathrm{opt}_i \leqq 6;\ 0 \leqq x'_i < 2^{30}\right)$,opti 代表第 i 次操作的种类,xi′ 代表第 i 次操作加密后的操作数。
记 last 为最近一次操作 3,4,5,6 得到的答案,初始时 last=0;操作 1,2 不会改变 last。第 i 次操作的真实操作数 xi=xi′xorlast,其中 last 取执行第 i 次操作前的值。
输出格式
在一行上输出一个整数,代表所有操作 3,4,5,6 的答案的按位异或和。若不存在这类操作,输出 0。
测试样例
6 7
1 1 4 5 1 4
2 1
1 9
4 1
5 8
3 13
6 7
1 4
6
样例 1 解释
按解密规则还原后,输入等价于:
6 7
1 1 4 5 1 4
2 1
1 9
4 1
5 9
3 8
6 1
1 0
初始时 M={1,1,1,4,4,5},各次操作如下:
∙第 1 次操作(种类 2,x=1):删除一个 1,M={1,1,4,4,5};
∙第 2 次操作(种类 1,x=9):插入 9,M={1,1,4,4,5,9};
∙第 3 次操作(种类 4,x=1):第 1 小的数为 1,答案为 1,last=1;
∙第 4 次操作(种类 5,x=9):9 的前驱为 5,答案为 5,last=5;
∙第 5 次操作(种类 3,x=8):M 中比 8 小的数有 5 个,加一得 6,答案为 6,last=6;
∙第 6 次操作(种类 6,x=1):1 的后继为 4,答案为 4,last=4;
∙第 7 次操作(种类 1,x=0):插入 0,M={0,1,1,4,4,5,9}。
四个答案的异或和为 $1 \operatorname{xor} 5 \operatorname{xor} 6 \operatorname{xor} 4 = 6$。
6 6
2 4 4 7 9 10
3 5
1 2
5 2
4 6
6 0
2 15
2
样例 2 解释
按解密规则还原后,输入等价于:
6 6
2 4 4 7 9 10
3 5
1 6
5 6
4 2
6 4
2 9
初始时 M={2,4,4,7,9,10},各次操作如下:
∙第 1 次操作(种类 3,x=5):比 5 小的数有 3 个,加一得 4,last=4;
∙第 2 次操作(种类 1,x=6):插入 6,M={2,4,4,6,7,9,10};
∙第 3 次操作(种类 5,x=6):6 的前驱为 4,last=4;
∙第 4 次操作(种类 4,x=2):第 2 小的数为 4,last=4;
∙第 5 次操作(种类 6,x=4):4 的后继为 6,last=6;
∙第 6 次操作(种类 2,x=9):删除一个 9,M={2,4,4,6,7,10}。
四个答案的异或和为 $4 \operatorname{xor} 4 \operatorname{xor} 4 \operatorname{xor} 6 = 2$。
提示
对于 100% 的数据,1≦n≦105,1≦m≦106,0≦ai,x<230。
本题输入数据较大,请使用较快的读入方式。