#2302. 「NOI2017」整数

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: samzhang

题目描述

在人类智慧的山巅,有着一台字长为 1048576 位的超级计算机,著名理论计算机科学家 P 博士正用它进行各种研究。 不幸的是,这天台风切断了电力系统,超级计算机无法工作,而 P 博士明天就要交实验结果了,只好求助于学过 OI 的你……

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 )。 对于加法操作,没有任何输出。

样例

样例输入 1

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

样例输出 1

0
1
0
1
0

样例解释 1

样例中有 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

样例 2

见附加文件下的 ex_2.inex_2.ans。 该组样例的数据范围同第 7 个测试点。

样例 3

见附加文件下的 ex_3.inex_3.ans。 该组样例的数据范围同第 13 个测试点。

样例 4

见附加文件下的 ex_4.inex_4.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 3 1 2
2 100 2
3 2000
4 4000 1 3
5 6000 3 1
6 8000 2 2
7 9000 3 4
8 10000 3
9 30000 4
10 50000 1
11 60000 3 2
12 65000 2 4
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 3 3
23 960000 4 1
24 990000 3 2
25 1000000 4