← 返回题目列表

Codeforces · 1515/H

H. 凤凰和比特

中文机器翻译题面 查看原题

Phoenix 喜欢玩位——具体来说,就是使用按位运算 AND、OR 和 XOR。他有 $$$n$$$ 个整数 $$$a_1, a_2, \dots, a_n$$$,并将执行 $$$q$$$ 以下查询:

1. 将 $$$l \le a_i \le r$$$ 处的所有数字 $$$a_i$$$ 替换为 $$$a_i$$$ AND $$$x$$$;
2. 将 $$$l \le a_i \le r$$$ 处的所有数字 $$$a_i$$$ 替换为 $$$a_i$$$ 或 $$$x$$$;
3. 将 $$$l \le a_i \le r$$$ 处的所有数字 $$$a_i$$$ 替换为 $$$a_i$$$ XOR $$$x$$$;
4.输出多少个不同的整数$$$a_i$$$,其中$$$l \le a_i \le r$$$。

对于每个查询,Phoenix 都会获得 $$$l$$$、$$$r$$$ 和 $$$x$$$。请注意,他考虑的是数字的值,而不是它们的指数。

输入

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le q \le 10^5$$$) - 分别是整数的数量和查询的数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i < 2^{20}$$$) - Phoenix 开头的整数。

接下来的 $$$q$$$ 行包含查询。对于每个查询,每行的第一个整数是 $$$t$$$ ($$$1 \le t \le 4$$$) — 查询的类型。

如果 $$$t \in \{1, 2, 3\}$$$,则后面将是三个整数 $$$l_i$$$、$$$r_i$$$ 和 $$$x_i$$$ ($$$0 \le l_i, r_i, x_i < 2^{20}$$$; $$$l_i \le r_i$$$)。

否则,如果 $$$t=4$$$,则后面将有两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$0 \le l_i \le r_i < 2^{20}$$$)。

保证至少有一个$$$t=4$$$ 的查询。

输出

打印每个查询的答案,其中 $$$t=4$$$。

示例

输入 #1

5 6
5 4 3 2 1
1 2 3 2
4 2 5
3 2 5 3
4 1 6
2 1 1 8
4 8 10

输出 #1

3
2
1

输入 #2

6 7
6 0 2 3 2 7
1 0 4 3
2 6 8 4
4 0 7
3 2 5 3
1 0 1 2
4 0 3
4 2 7

输出 #2

5
1
2

注意

在第一个示例中:

- 对于第一个查询,$$$2$$$ 替换为 $$$2$$$ AND $$$2 = 2$$$,$$$3$$$ 替换为 $$$3$$$ AND $$$2 = 2$$$。这组数字是 $$$\{1, 2, 4, 5\}$$$。
- 对于第二个查询,$$$2$$$ 和 $$$5$$$ 之间有 $$$3$$$ 不同的数字:$$$2$$$、$$$4$$$ 和 $$$5$$$。
- 对于第三个查询,$$$2$$$ 替换为 $$$2$$$ XOR $$$3 = 1$$$,$$$4$$$ 替换为 $$$4$$$ XOR $$$3 = 7$$$,$$$5$$$ 替换为 $$$5$$$ XOR $$$3 = 6$$$。这组数字是 $$$\{1, 6, 7\}$$$。
- 对于第四个查询,$$$1$$$ 和 $$$6$$$ 之间有 $$$2$$$ 不同的数字:$$$1$$$ 和 $$$6$$$。
- 对于第五个查询,$$$1$$$ 替换为 $$$1$$$ OR $$$8 = 9$$$。这组数字是 $$$\{6, 7, 9\}$$$。
- 对于第六个查询,$$$8$$$ 和 $$$10$$$ 之间有一个不同的数字:$$$9$$$。