LG#P6136. 【模板】普通平衡树

【模板】普通平衡树

P6136 【模板】普通平衡树(数据加强版)

题目描述

\hspace{15pt}你需要动态地维护一个可重集合 MM,并支持以下六种操作:

1. {\hspace{20pt}}_\texttt{1.}\,向 MM 中插入一个数 xx;

2. {\hspace{20pt}}_\texttt{2.}\,从 MM 中删除一个数 xx。若 MM 中有多个 xx,只删除其中一个;

3. {\hspace{20pt}}_\texttt{3.}\,查询 MM 中有多少个数比 xx 小,并将得到的答案加一;

4. {\hspace{20pt}}_\texttt{4.}\,将 MM 中的数从小到大排列,查询排名第 xx 位的数;

5. {\hspace{20pt}}_\texttt{5.}\,查询 MM 中 xx 的前驱,前驱定义为小于 xx 且最大的数;

6. {\hspace{20pt}}_\texttt{6.}\,查询 MM 中 xx 的后继,后继定义为大于 xx 且最小的数。

\hspace{15pt}本题强制在线:每次操作的真实操作数 xx 需要由输入给出的加密值解密得到。保证所有操作合法,即操作 22 时 MM 中至少存在一个 xx,操作 44 时存在排名第 xx 位的数,操作 5,65, 6 时分别存在 xx 的前驱和后继。

输入格式

\hspace{15pt}第一行输入两个整数 $n, m \left(1 \leqq n \leqq 10^5;\ 1 \leqq m \leqq 10^6\right)$ 代表初始数的个数与操作次数。

\hspace{15pt}第二行输入 nn 个整数 $a_1, a_2, \dots, a_n \left(0 \leqq a_i < 2^{30}\right)$ 代表初始时 MM 中的数。

\hspace{15pt}此后 mm 行,第 ii 行输入两个整数 $\mathrm{opt}_i, x'_i \left(1 \leqq \mathrm{opt}_i \leqq 6;\ 0 \leqq x'_i < 2^{30}\right)$,opti\mathrm{opt}_i 代表第 ii 次操作的种类,xi′x'_i 代表第 ii 次操作加密后的操作数。

\hspace{15pt}记 last\mathrm{last} 为最近一次操作 3,4,5,63, 4, 5, 6 得到的答案,初始时 last=0\mathrm{last} = 0;操作 1,21, 2 不会改变 last\mathrm{last}。第 ii 次操作的真实操作数 xi=xi′xor⁡lastx_i = x'_i \operatorname{xor} \mathrm{last},其中 last\mathrm{last} 取执行第 ii 次操作前的值。

输出格式

\hspace{15pt}在一行上输出一个整数,代表所有操作 3,4,5,63, 4, 5, 6 的答案的按位异或和。若不存在这类操作,输出 00。

测试样例

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

样例 1 解释

\hspace{15pt}按解密规则还原后,输入等价于:

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

\hspace{15pt}初始时 M={1,1,1,4,4,5}M = \{1, 1, 1, 4, 4, 5\},各次操作如下:

∙ \hspace{23pt}\bullet\,第 11 次操作(种类 22,x=1x = 1):删除一个 11,M={1,1,4,4,5}M = \{1, 1, 4, 4, 5\};

∙ \hspace{23pt}\bullet\,第 22 次操作(种类 11,x=9x = 9):插入 99,M={1,1,4,4,5,9}M = \{1, 1, 4, 4, 5, 9\};

∙ \hspace{23pt}\bullet\,第 33 次操作(种类 44,x=1x = 1):第 11 小的数为 11,答案为 11,last=1\mathrm{last} = 1;

∙ \hspace{23pt}\bullet\,第 44 次操作(种类 55,x=9x = 9):99 的前驱为 55,答案为 55,last=5\mathrm{last} = 5;

∙ \hspace{23pt}\bullet\,第 55 次操作(种类 33,x=8x = 8):MM 中比 88 小的数有 55 个,加一得 66,答案为 66,last=6\mathrm{last} = 6;

∙ \hspace{23pt}\bullet\,第 66 次操作(种类 66,x=1x = 1):11 的后继为 44,答案为 44,last=4\mathrm{last} = 4;

∙ \hspace{23pt}\bullet\,第 77 次操作(种类 11,x=0x = 0):插入 00,M={0,1,1,4,4,5,9}M = \{0, 1, 1, 4, 4, 5, 9\}。

\hspace{15pt}四个答案的异或和为 $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 解释

\hspace{15pt}按解密规则还原后,输入等价于:

6 6
2 4 4 7 9 10
3 5
1 6
5 6
4 2
6 4
2 9

\hspace{15pt}初始时 M={2,4,4,7,9,10}M = \{2, 4, 4, 7, 9, 10\},各次操作如下:

∙ \hspace{23pt}\bullet\,第 11 次操作(种类 33,x=5x = 5):比 55 小的数有 33 个,加一得 44,last=4\mathrm{last} = 4;

∙ \hspace{23pt}\bullet\,第 22 次操作(种类 11,x=6x = 6):插入 66,M={2,4,4,6,7,9,10}M = \{2, 4, 4, 6, 7, 9, 10\};

∙ \hspace{23pt}\bullet\,第 33 次操作(种类 55,x=6x = 6):66 的前驱为 44,last=4\mathrm{last} = 4;

∙ \hspace{23pt}\bullet\,第 44 次操作(种类 44,x=2x = 2):第 22 小的数为 44,last=4\mathrm{last} = 4;

∙ \hspace{23pt}\bullet\,第 55 次操作(种类 66,x=4x = 4):44 的后继为 66,last=6\mathrm{last} = 6;

∙ \hspace{23pt}\bullet\,第 66 次操作(种类 22,x=9x = 9):删除一个 99,M={2,4,4,6,7,10}M = \{2, 4, 4, 6, 7, 10\}。

\hspace{15pt}四个答案的异或和为 $4 \operatorname{xor} 4 \operatorname{xor} 4 \operatorname{xor} 6 = 2$。

提示

\hspace{15pt}对于 100%100\% 的数据,1≦n≦1051 \leqq n \leqq 10^5,1≦m≦1061 \leqq m \leqq 10^6,0≦ai,x<2300 \leqq a_i, x < 2^{30}。

\hspace{15pt}本题输入数据较大,请使用较快的读入方式。