T161995 可持久化完全动态图上树状数组维护 01 背包转移

“你这样写题目名字是要向全国人民谢罪的。” $\text N$ 老师对 $\text{zxy}$ 哔哔说。

众所周知，洛谷有一道题叫《普通平衡树》，是洛谷最著名的高级数据结构模板。但 普通平衡树太普通了，不符合银临女神出众的气质，因此扶苏希望你写一棵《特殊平衡树》。 您需要写一个可重集，来维护一些数，其中需要提供以下操作： 1. 插入一个值为 $x$ 的数。 2. 删除一个值为 $x$ 的数(如果没有这个数，则不删除)。 3. 求集合中最大的数(如果集合为空，输出 $\text{zay}$)。 4. 求集合中最小的数(如果集合为空，输出 $\text{zay}$)。 5. 求 $x$ 的前驱(前驱定义为小于 $x$，且最大的数；如果没有前驱，输出 $\text{cuc}$)。 6. 求 $x$ 的后继(后继定义为大于 $x$，且最小的数；如果没有后继，输出 $\text{cyc}$)。 7. 将目前集合中的所有数字都加上 $x$。 可重集是一个集合，但是集合中的元素可以重复。例如，{1,1,4,5,1,4} 是一个可重 集；{1,2} 也是一个可重集；向可重集 {1,2} 插入一个数字 2 后的集合为 {1,2,2}。

输入的第一行是一个整数 $n$，表示操作的条数。 为了体现本题的特殊性，本题采用强制在线的方式读入数据。具体来说，你需要维护一个整数 $lastans$，这个数表示你上次输出的答案，初始时为 $0$。 每次进行输出时，如果输出的不是一个字符串，则你需要将 $lastans$ 赋值为你本次的输出。 接下来 $n$ 行，每行一个或两个整数，表示一次操作。第一个数为 $opt$。 $opt⊗lastans$ 的值为表示本次操作的编号。其中 $⊗$ 表示按位异或运算符，即 $\text{C++}$ 语言的「^」运算符。 • 若编号为 $3$ 或 $4$，则该行只有一个数字，表示一次查询。 • 否则接下来有一个整数，表示给定的 $x$。

对于每次查询操作，输出一行一个整数表示答案。

本题共有 $16$ 个测试点，每个测试点 $?$ 分。 |测试点编号 | $n$ |特殊性质 | | -----------: | -----------: | -----------: | |$1$ | $114514$ | 没有 $3,4,5,6$ 操作 | | $2$ ~ $6$ | $1001$ | 无 | | $7$ ~ $9$| $100002$ | 只有前四个操作 | | $10$ ~ $12$| $100003$ | 只有前六个操作 | | $13$ ~ $16$| $1000005$ | 没有特殊性质 | 对于全部的测试点，保证 $opt⊗ lastans$ 的值是 $[1, 7]$ 范围内的整数；$0 \leq x < 2 ^ {63}$。 任意时刻集合中的数都是在 $[0, 2 ^ {63}]$ 范围内的整数；对于 $5、6$ 两个操作，不保证给出的 $x$ 存在于集合中。 【提示】 $n$ 的数值可以快速帮你判断测试点所具有的特殊性质。