102614: [AtCoder]ABC261 E - Many Operations
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：5
Solved：0
Description
Score : $500$ points
Problem Statement
We have a variable $X$ and $N$ kinds of operations that change the value of $X$. Operation $i$ is represented as a pair of integers $(T_i,A_i)$, and is the following operation:
- if $T_i=1$, it replaces the value of $X$ with $X\ {\rm and}\ A_i$;
- if $T_i=2$, it replaces the value of $X$ with $X\ {\rm or}\ A_i$;
- if $T_i=3$, it replaces the value of $X$ with $X\ {\rm xor}\ A_i$.
Initialize $X$ with the value of $C$ and execute the following procedures in order:
- Perform Operation $1$, and then print the resulting value of $X$.
- Next, perform Operation $1, 2$ in this order, and then print the value of $X$.
- Next, perform Operation $1, 2, 3$ in this order, and then print the value of $X$.
- $\vdots$
- Next, perform Operation $1, 2, \ldots, N$ in this order, and then print the value of $X$.
What are ${\rm and}, {\rm or}, {\rm xor}$?
The ${\rm and}, {\rm or}, {\rm xor}$ of non-negative integers $A$ and $B$ are defined as follows:
- When $A\ {\rm and}\ B$ is written in base two, the digit in the $2^k$'s place ($k \geq 0$) is $1$ if both of the digits in that place of $A$ and $B$ are $1$, and $0$ otherwise.
- When $A\ {\rm or}\ B$ is written in base two, the digit in the $2^k$'s place ($k \geq 0$) is $1$ if at least one of the digits in that place of $A$ and $B$ is $1$, and $0$ otherwise.
- When $A\ {\rm xor}\ B$ is written in base two, the digit in the $2^k$'s place ($k \geq 0$) is $1$ if exactly one of the digits in that place of $A$ and $B$ is $1$, and $0$ otherwise.
Constraints
- $1 \leq N \leq 2\times 10^5$
- $1\leq T_i \leq 3$
- $0\leq A_i \lt 2^{30}$
- $0\leq C \lt 2^{30}$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $C$ $T_1$ $A_1$ $T_2$ $A_2$ $\vdots$ $T_N$ $A_N$
Output
Print $N$ lines, as specified in the Problem Statement.
Sample Input 1
3 10 3 3 2 5 1 12
Sample Output 1
9 15 12
The initial value of $X$ is $10$.
- Operation $1$ changes $X$ to $9$.
- Next, Operation $1$ changes $X$ to $10$, and then Operation $2$ changes it to $15$.
- Next, Operation $1$ changes $X$ to $12$, and then Operation $2$ changes it to $13$, and then Operation $3$ changes it to $12$.
Sample Input 2
9 12 1 1 2 2 3 3 1 4 2 5 3 6 1 7 2 8 3 9
Sample Output 2
0 2 1 0 5 3 3 11 2
Input
题意翻译
我们有一个正整数 $X$ ，当然还有 $N$ 条位运算操作，按照 $T_i\ A_i$ 输入，其中 + $T_i=1$ 表示该操作为 $\operatorname{and}$； + $T_i=2$ 表示该操作为 $\operatorname{or}$； + $T_i=3$ 表示该操作为 $\operatorname{xor}$。 第 $i$ 条操作把当前的 $X$ 执行 $1,2,\cdots ,i$ 共 $i$ 条操作。 执行完成后输出 $X$ 的值。Output
分数：500分
部分
问题描述
我们有一个变量$X$和$N$种可以改变$X$值的操作。操作$i$用一对整数$(T_i,A_i)$表示，表示以下操作：
- 如果$T_i=1$，则用$X\ {\rm and}\ A_i$替换$X$的值；
- 如果$T_i=2$，则用$X\ {\rm or}\ A_i$替换$X$的值；
- 如果$T_i=3$，则用$X\ {\rm xor}\ A_i$替换$X$的值。
- 执行操作$1$，然后打印$X$的结果值。
- 接下来，按顺序执行操作$1, 2$，然后打印$X$的值。
- 接下来，按顺序执行操作$1, 2, 3$，然后打印$X$的值。
- $\vdots$
- 接下来，按顺序执行操作$1, 2, \ldots, N$，然后打印$X$的值。
什么是${\rm and}, {\rm or}, {\rm xor}$？
非负整数$A$和$B$的${\rm and}, {\rm or}, {\rm xor}$定义如下：
- 当$A\ {\rm and}\ B$写成二进制时，$2^k$位（$k \geq 0$）的数字为1，当$A$和$B$中该位的数字都为1时，否则为0。
- 当$A\ {\rm or}\ B$写成二进制时，$2^k$位（$k \geq 0$）的数字为1，当$A$和$B$中该位的数字至少有一个为1时，否则为0。
- 当$A\ {\rm xor}\ B$写成二进制时，$2^k$位（$k \geq 0$）的数字为1，当$A$和$B$中该位的数字恰好有一个为1时，否则为0。
约束条件
- $1 \leq N \leq 2\times 10^5$
- $1\leq T_i \leq 3$
- $0\leq A_i \lt 2^{30}$
- $0\leq C \lt 2^{30}$
- 输入中的所有值都是整数。
输入
输入从标准输入以以下格式给出：
$N$ $C$ $T_1$ $A_1$ $T_2$ $A_2$ $\vdots$ $T_N$ $A_N$
输出
按问题描述中指定的格式打印$N$行。
样例输入1
3 10 3 3 2 5 1 12
样例输出1
9 15 12
$X$的初始值为$10$。
- 操作$1$将$X$改为$9$。
- 接下来，操作$1$将$X$改为$10$，然后操作$2$将其改为$15$。
- 接下来，操作$1$将$X$改为$12$，然后操作$2$将其改为$13$，然后操作$3$将其改为$12$。
样例输入2
9 12 1 1 2 2 3 3 1 4 2 5 3 6 1 7 2 8 3 9
样例输出2
0 2 1 0 5 3 3 11 2