【NOI2017】整数 排行榜

---

时间限制： 2 s
空间限制： 524288 KB

题目描述

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$ 的具体含义见子任务。

输出格式

输出到标准输出。

对于每个询问操作，输出一行，表示该询问的答案（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$ 。

子任务

在所有测试点中，$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$ 的测试点，不保证询问操作和修改操作的先后顺序

测试点编号	$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

题目来源

NOI 2017 Day 1

---

---