QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 128 MB Total points: 100

# 7463. y-fast trie

Statistics

给定一个常数 $C$,你需要维护一个集合 $S$,支持 $n$ 次操作:

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

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

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

输入格式

第一行两个整数 $n, C$。

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

输出格式

输出 $n$ 行,第 $i$ 行表示第 $i$ 次操作结束后的答案。

样例数据

样例输入

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。

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

对于另外 $19\%$ 的数据,$n\leq 500$。

对于另外 $19\%$ 的数据,$n\leq 10^4$。

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

对于 $100\%$ 的数据,$1\leq n \leq 5\times 10^5$,$1\leq C\leq 1073741823$,$0\leq x\leq 1073741823$。