A6033. 「2017 山东二轮集训 Day2」第三题
编程题
提高+/省选-
知识点
题目描述
小火车觉得对生活已经没有什么好留恋的了，于是决定前往二次元去寻找真爱。
但是跨越次元是不被神所允许的，小火车决定和神进行比赛，神给了他一个题，你能帮忙解出来吗？
从前有三堆集合分别是 $ \{ A_i \}, \{ B_i \}, \{ C_i \} $ 我们认为 $ B_i = (\mathop{\cap}\limits_{j \in A_i} B_j) \cup C_i $ 而 $ A_i $ 里的元素一定小于 $ i $ 任意时刻两个不同的 $ C $ 集合的交集为空，现在神告诉你 $ A $ 集合以及 $ C $ 集合的大小，你能告诉他对于我的询问集合 $ S $，$ |\mathop{\cup}\limits_{i \in S} B_i| $ 是多少么。
实际上你要支持的操作如下：
1. 给定集合 $ A $，令 $ n $ 加一，多了个新的 $ A_n $ 和 $ B_n $，$ C_n $ 的大小为 $ k $；
2. 把 $ C_i $ 的大小改成为 $ k $；
3. 询问集合 $ S $；
但是跨越次元是不被神所允许的，小火车决定和神进行比赛，神给了他一个题，你能帮忙解出来吗？
从前有三堆集合分别是 $ \{ A_i \}, \{ B_i \}, \{ C_i \} $ 我们认为 $ B_i = (\mathop{\cap}\limits_{j \in A_i} B_j) \cup C_i $ 而 $ A_i $ 里的元素一定小于 $ i $ 任意时刻两个不同的 $ C $ 集合的交集为空，现在神告诉你 $ A $ 集合以及 $ C $ 集合的大小，你能告诉他对于我的询问集合 $ S $，$ |\mathop{\cup}\limits_{i \in S} B_i| $ 是多少么。
实际上你要支持的操作如下：
1. 给定集合 $ A $，令 $ n $ 加一，多了个新的 $ A_n $ 和 $ B_n $，$ C_n $ 的大小为 $ k $；
2. 把 $ C_i $ 的大小改成为 $ k $；
3. 询问集合 $ S $；
输入格式
第一行一个正整数 $ m $ 表示操作总数，接下来 $ m $ 行每行一个操作。
如果是 1 号操作，格式为 $ \texttt{Add t} $ 后跟 $ t $ 个整数，$ t $ 表示 $ A_n $ 的大小，$ t $ 个整数表示集合 $ A_n $。
如果是 2 号操作，格式为 $ \texttt{Update i k} $；
如果是 3 号操作，格式为 $ \texttt{Query t} $ 后跟 $ t $ 个整数，含义同上。
数据保证合法。为了体现程序的在线性 $ 1 $ 号操作集合里的元素都需要异或上上次的答案，初值为 $ 0 $（注意 $ t $ 不需要）。
如果是 1 号操作，格式为 $ \texttt{Add t} $ 后跟 $ t $ 个整数，$ t $ 表示 $ A_n $ 的大小，$ t $ 个整数表示集合 $ A_n $。
如果是 2 号操作，格式为 $ \texttt{Update i k} $；
如果是 3 号操作，格式为 $ \texttt{Query t} $ 后跟 $ t $ 个整数，含义同上。
数据保证合法。为了体现程序的在线性 $ 1 $ 号操作集合里的元素都需要异或上上次的答案，初值为 $ 0 $（注意 $ t $ 不需要）。
输出格式
对于每个 3 号操作输出一行一个整数表示答案。
输入输出样例
输入 #1
4 Add 0 1 Query 1 1 Update 1 4 Query 1 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 $。
对于 $ 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 $。