#P3822. [NOI2017] 整数

    ID: 54 远端评测题 2000ms 500MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>高精度2017线段树NOI 系列O2优化进制

[NOI2017] 整数

题目背景

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

题目描述

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

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

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

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

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

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

输入格式

输入的第一行包含四个正整数 n,t1,t2,t3n,t_1,t_2,t_3nn 的含义见题目描述,t1t_1t2t_2t3t_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

提示

在所有测试点中,$1\leqslant t_1 \leqslant 3, 1 \leqslant t_2 \leqslant 4, 1 \leqslant t_3 \leqslant 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| \leqslant 10^9
  • 对于 t2=1t_2 = 1 的测试点,满足 0b,k300 \leqslant b, k \leqslant 30
  • 对于 t2=2t_2 = 2 的测试点,满足 0b,k1000 \leqslant b, k \leqslant 100
  • 对于 t2=3t_2 = 3 的测试点,满足 0b,kn0 \leqslant b, k \leqslant n
  • 对于 t2=4t_2 = 4 的测试点,满足 0b,k30n0 \leqslant b, k \leqslant 30n
  • 对于 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