#1807. 「NOI2017」整数

「NOI2017」整数

题目描述

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

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

具体来说,有一个整数 xx ,一开始为 00

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

  • 1 aa bb :将 xx 加上整数 a2ba \cdot 2 ^ b,其中 aa 为一个整数,bb 为一个非负整数

  • 2 kk :询问 xx 在用二进制表示时,位权为 2k2 ^ k 的位的值(即这一位上的 11 代表 2k2 ^ k

保证在任何时候,x0x \ge 0

输入格式

从标准输入读入数据。

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

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

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

输出格式

输出到标准输出。

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

样例

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
0
1
0
1
0

样例中有 1010 个操作: 第 11 个为将 xx 加上 100×20100 \times 2^0 ,操作后, x=100x= 100

22 个为将 xx 加上 2333×202333 \times 2^0 ,操作后, x=2433x= 2433

33 个为将 xx 加上 233×20-233 \times 2^0 ,操作后, x=2200x= 2200

44 个为询问 xx 位权为 252^5 的位上的值, xx 在二进制下为 100010011000100010011000 ,答案为 00

55 个为询问 xx 位权为 272^7 的位上的值, xx 在二进制下为 100010011000100010011000 ,答案为 11

66 个为询问 xx 位权为 2152^{15} 的位上的值, xx 在二进制下为 100010011000100010011000 ,答案为 00

77 个为将 xx 加上 5×215=1638405 \times 2^{15} = 163840 ,操作后, x=166040x= 166040

88 个为询问 xx 位权为 2152^{15} 的位上的值, xx 在二进制下为 101000100010011000101000100010011000 ,答案为 11

99 个为将 xx 加上 1×212=4096-1 \times 2^{12} = -4096 ,操作后, x=161944x= 161944

1010 个为询问 xx 位权为 2152^{15} 的位上的值, xx 在二进制下为 100111100010011000100111100010011000 ,答案为 00

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

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

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

数据范围与提示

子任务

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

  • 对于 t1=1t_1 = 1 的测试点,满足 a=1a = 1

  • 对于 t1=2t_1 = 2 的测试点,满足 a=1|a| = 1

  • 对于 t1=3t_1 = 3 的测试点,满足 a109|a| \le 10 ^ 9

  • 对于 t2=1t_2 = 1 的测试点,满足 0b,k300 \le b,k \le 30

  • 对于 t2=2t_2 = 2 的测试点,满足 0b,k1000 \le b,k \le 100

  • 对于 t2=3t_2 = 3 的测试点,满足 0b,kn0 \le b,k \le n

  • 对于 t2=4t_2 = 4 的测试点,满足 0b,k30n0 \le b,k \le 30 n

  • 对于 t3=1t_3 = 1 的测试点,保证所有询问操作都在所有修改操作之后

  • 对于 t3=2t_3 = 2 的测试点,不保证询问操作和修改操作的先后顺序

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

测试点编号 nn \le t1t_1 t2t_2 t3t_3
11 1010 33 11 22
22 100100 22
33 20002000
44 40004000 11 33
55 60006000 33 11
66 80008000 22 22
77 90009000 33 44
88 1000010000 33
99 3000030000 44
1010 5000050000 11
1111 6000060000 33 22
1212 6500065000 22 44
1313 7000070000 33
1414 200000200000
1515 300000300000 22
1616 400000400000 33
1717 500000500000 33
1818 600000600000 44
1919 700000700000
2020 800000800000 11
2121 900000900000 22
2222 930000930000 33 33
2323 960000960000 44 11
2424 990000990000 33 22
2525 10000001000000 44