「2017 山东二轮集训 Day2」第三题

传统 3000 ms 512 MiB

$34$ 通过 $79$ 提交

题目描述

小火车觉得对生活已经没有什么好留恋的了，于是决定前往二次元去寻找真爱。

但是跨越次元是不被神所允许的，小火车决定和神进行比赛，神给了他一个题，你能帮忙解出来吗？

从前有三堆集合分别是 $\{ A_i \}, \{ B_i \}, \{ C_i \}$，我们认为

$$B_i = \left(\bigcap_{j \in A_i} B_j\right) \cup C_i $$

而 $A_i$ 里的元素一定小于 $i$，任意时刻两个不同的 $C$ 集合的交集为空。现在神告诉你 $A$ 集合以及 $C$ 集合的大小，你能告诉他对于我的询问集合 $S$，

$$\left|\bigcup_{i \in S} B_i\right|$$

是多少么。

实际上你要支持的操作如下：

1. 给定集合 $A$，令 $n$ 加一，多了个新的 $A_n$ 和 $B_n$，$C_n$ 的大小为 $k$；
2. 把 $C_i$ 的大小改成为 $k$；
3. 询问集合 $S$；

输入格式

第一行一个正整数 $m$ 表示操作总数，接下来 $m$ 行每行一个操作。

• 如果是 1 号操作，格式为 Add t 后跟 $t$ 个整数，$t$ 表示 $A_n$ 的大小，$t$ 个整数表示集合 $A_n$。
• 如果是 2 号操作，格式为 Update i k；
• 如果是 3 号操作，格式为 Query t 后跟 $t$ 个整数，含义同上。

数据保证合法。为了体现程序的在线性，1 号操作集合里的元素都需要异或上上次的答案，初值为 $0$（注意 $t$ 不需要）。

输出格式

对于每个 3 号操作输出一行一个整数表示答案。

样例

输入

4
Add 0 1
Query 1 1
Update 1 4
Query 1 1

输出

1
4

数据范围与提示

用 $n$ 表示插入数量，用 $q$ 表示询问数量。

• 对于 $20\%$ 的数据，满足 $n, q \leq 50$，Update 操作数量为 $0$，$A$ 集合和询问集合总大小 $\leq 700$；
• 对于 $40\%$ 的数据，满足 $n, q \leq 1000$，Update 操作数量为 $0$，$A$ 集合和询问集合总大小 $\leq 20000$；
• 对于 $100\%$ 的数据，满足 $n \leq 200000, q \leq 100000$，Update 操作数量 $\leq 100000$，$A$ 集合和询问集合总大小 $\leq 600000$； $k \leq 1000$。