UOJ Logo Universal Online Judge

UOJ

#314. 【NOI2017】整数

统计

P 博士将他的计算任务抽象为对一个整数的操作。

具体来说,有一个整数 $x$ ,一开始为0。

接下来有 $n$ 个操作,每个操作都是以下两种类型中的一种:

  • 1 $a$ $b$ :将 $x$ 加上整数 $a \cdot 2 ^ b$,其中 $a$ 为一个整数,$b$ 为一个非负整数
  • 2 $k$ :询问 $x$ 在用二进制表示时,位权为 $2 ^ k$ 的位的值(即这一位上的 $1$ 代表 $2 ^ k$ )

保证在任何时候,$x \ge 0$。

输入格式

从标准输入读入数据。

输入的第一行包含四个正整数 $n, t_1, t_2, t_3$,$n$ 的含义见题目描述,$t_1, t_2, t_3$ 的具体含义见子任务。

接下来 $n$ 行,每行给出一个操作,具体格式和含义见题目描述。

同一行输入的相邻两个元素之间,用恰好一个空格隔开。

输出格式

输出到标准输出。

对于每个询问操作,输出一行,表示该询问的答案(0或1)。 对于加法操作,没有任何输出。

样例一

input

10 3 1 2
1 100 0
1 2333 0
1 -233 0
2 5
2 7
2 15
1 5 15
2 15
1 -1 12
2 15

output

0
1
0
1
0

explanation

样例中有 $10$ 个操作: 第 $1$ 个为将 $x$ 加上 $100 \times 2^0$ ,操作后, $x= 100$ ;

第 $2$ 个为将 $x$ 加上 $2333 \times 2^0$ ,操作后, $x= 2433$ ;

第 $3$ 个为将 $x$ 加上 $-233 \times 2^0$ ,操作后, $x= 2200$ ;

第 $4$ 个为询问 $x$ 位权为 $2^5$ 的位上的值, $x$ 在二进制下为 $100010011000$ ,答案为 $0$ ;

第 $5$ 个为询问 $x$ 位权为 $2^7$ 的位上的值, $x$ 在二进制下为 $100010011000$ ,答案为 $1$ ;

第 $6$ 个为询问 $x$ 位权为 $2^{15}$ 的位上的值, $x$ 在二进制下为 $100010011000$ ,答案为 $0$ ;

第 $7$ 个为将 $x$ 加上 $5 \times 2^{15} = 163840$ ,操作后, $x= 166040$ ;

第 $8$ 个为询问 $x$ 位权为 $2^{15}$ 的位上的值, $x$ 在二进制下为 $101000100010011000$ ,答案为 $1$ ;

第 $9$ 个为将 $x$ 加上 $-1 \times 2^{12} = -4096$ ,操作后, $x= 161944$ ;

第 $10$ 个为询问 $x$ 位权为 $2^{15}$ 的位上的值, $x$ 在二进制下为 $100111100010011000$ ,答案为 $0$ 。

样例二

见下载文件中的 ex_integer2.inex_integer2.ans。 该组样例的数据范围同第7个测试点。

样例三

见下载文件中的 ex_integer3.inex_integer3.ans。 该组样例的数据范围同第13个测试点。

样例四

见下载文件中的 ex_integer4.inex_integer4.ans。 该组样例的数据范围同第14个测试点。

限制与约定

在所有测试点中,$1 \le t_1 \le 3, 1 \le t_2 \le 4, 1 \le t_3 \le 2$。 不同的 $t_1, t_2, t_3$ 对应的特殊限制如下:

  • 对于 $t_1 = 1$ 的测试点,满足 $a = 1$
  • 对于 $t_1 = 2$ 的测试点,满足 $|a| = 1$
  • 对于 $t_1 = 3$ 的测试点,满足 $|a| \le 10 ^ 9$
  • 对于 $t_2 = 1$ 的测试点,满足 $0 \le b,k \le 30$
  • 对于 $t_2 = 2$ 的测试点,满足 $0 \le b,k \le 100$
  • 对于 $t_2 = 3$ 的测试点,满足 $0 \le b,k \le n$
  • 对于 $t_2 = 4$ 的测试点,满足 $0 \le b,k \le 30 n$
  • 对于 $t_3 = 1$ 的测试点,保证所有询问操作都在所有修改操作之后
  • 对于 $t_3 = 2$ 的测试点,不保证询问操作和修改操作的先后顺序

本题共25个测试点,每个测试点4分。各个测试点的数据范围如下:

测试点编号$n \le$$t_1$$t_2$$t_3$
1$10$312
2$100$2
3$2000$
4$4000$13
5$6000$31
6$8000$22
7$9000$34
8$10000$3
9$30000$4
10$50000$1
11$60000$32
12$65000$24
13$70000$3
14$200000$
15$300000$2
16$400000$3
17$500000$3
18$600000$4
19$700000$
20$800000$1
21$900000$2
22$930000$33
23$960000$41
24$990000$32
25$1000000$4

时间限制:$2\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载