#P6105. [Ynoi2010] y-fast trie

[Ynoi2010] y-fast trie

题目背景

谔谔我

本题读入量约 6 MB,输出量约 5 MB,请选择适合的输入输出方法

题目描述

给定一个常数 CC,你需要维护一个集合 SS,支持 nn 次操作:

  • 操作1:给出 xx,插入一个元素 xx,保证之前集合中没有 xx 这个元素
  • 操作2:给出 xx,删除一个元素 xx,保证之前集合中存在 xx 这个元素

每次操作结束后,需要输出 $\max\limits_{\substack{ i, j \in S \\ i \ne j }} \bigl( (i+j) \bmod C \bigr)$,即从 SS 集合中选出两个不同的元素,其的和 mod C\bmod~C 的最大值,如果 SS 集合中不足两个元素,则输出 EE

本题强制在线,每次的 xx 需要 xor\operatorname{xor} 上上次答案 ,如果之前没有询问或者输出了 EE,则上次答案为 00

输入格式

第一行两个整数 n,Cn, C

接下来 nn 行,每行有两个整数 1 x1~x2 x2~x,表示第一类或第二类操作。

输出格式

输出 nn 行,第 ii 行表示第 ii 次操作结束后的答案。

7 9
1 2
1 3
1 0
1 14
2 14
2 13
1 1

EE
5
8
8
8
5
7

提示

Idea:zhouwc,Solution:ccz181078&nzhtl1477,Code:ccz181078&nzhtl1477,Data:nzhtl1477

注意:本题采用捆绑测试,只有当你通过一个 subtask 中的所有测试点后,你才能拿到这个 subtask 的分数。

对于其中 1%1\% 的数据,为样例 1。

对于另外 9%9\% 的数据,集合中元素个数 1\le 1

对于另外 19%19\% 的数据,n500n\leq 500

对于另外 19%19\% 的数据,n104n\leq 10^4

对于另外 19%19\% 的数据,1n,C1051\leq n,C \leq 10^5

对于 100%100\% 的数据,1n5×1051\leq n \leq 5\times 10^51C10737418231\leq C\leq 10737418230x10737418230\leq x\leq 1073741823