TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P4723
  • Problem
  • P4723「2017 山东二轮集训 Day2」第三题
    Limits : Time Limit : - MS   Memory Limit : - KB
    Judgment Tips : 3s 512m
    Description

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

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

    从前有三堆集合分别是 \(\\{ 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\)
    Input Format

    第一行一个正整数 \(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\) 不需要)。

    Output Format

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

    Sample Input

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

    Sample Output

    1
    4

    Hint

    \(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\)