CF1515H Phoenix and Bits

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$ OR $x$； 3. 将所有满足 $l \le a_i \le r$ 的数 $a_i$ 替换为 $a_i$ XOR $x$； 4. 输出所有满足 $l \le a_i \le r$ 的 $a_i$ 中有多少个不同的整数。 对于每个操作，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$ 的操作，输出一行答案。

在第一个样例中： - 第一个操作中，$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]$ 内有 $1$ 个不同的数：$9$。 由 ChatGPT 4.1 翻译