Phoenix and Bits

题意翻译

维护大小为 $n$ 的集合 $a$，$q$ 次操作： - `1 x y z`：将大小在 $x$ 到 $y$ 之间的数按位与 $z$。 - `2 x y z`：将大小在 $x$ 到 $y$ 之间的数按位或 $z$。 - `3 x y z`：将大小在 $x$ 到 $y$ 之间的数按位异或 $z$。 - `4 x y`：查询在 $x$ 到 $y$ 之间有多少个不同的数。 $1\leqslant n\leqslant 2\times 10^5$，$1\leqslant q\leqslant 10^5$。

题目描述

Phoenix loves playing with bits — specifically, by using the bitwise operations AND, OR, and XOR. He has $ n $ integers $ a_1, a_2, \dots, a_n $ , and will perform $ q $ of the following queries: 1. replace all numbers $ a_i $ where $ l \le a_i \le r $ with $ a_i $ AND $ x $ ; 2. replace all numbers $ a_i $ where $ l \le a_i \le r $ with $ a_i $ OR $ x $ ; 3. replace all numbers $ a_i $ where $ l \le a_i \le r $ with $ a_i $ XOR $ x $ ; 4. output how many distinct integers $ a_i $ where $ l \le a_i \le r $ . For each query, Phoenix is given $ l $ , $ r $ , and $ x $ . Note that he is considering the values of the numbers, not their indices.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ q $ ( $ 1 \le n \le 2 \cdot 10^5 $ ; $ 1 \le q \le 10^5 $ ) — the number of integers and the number of queries, respectively. The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 0 \le a_i < 2^{20} $ ) — the integers that Phoenix starts with. The next $ q $ lines contain the queries. For each query, the first integer of each line is $ t $ ( $ 1 \le t \le 4 $ ) — the type of query. If $ t \in \{1, 2, 3\} $ , then three integers $ l_i $ , $ r_i $ , and $ x_i $ will follow ( $ 0 \le l_i, r_i, x_i < 2^{20} $ ; $ l_i \le r_i $ ). Otherwise, if $ t=4 $ , two integers $ l_i $ and $ r_i $ will follow ( $ 0 \le l_i \le r_i < 2^{20} $ ). It is guaranteed that there is at least one query where $ t=4 $ .

输出格式

Print the answer for each query where $ 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

说明

In the first example: - For the first query, $ 2 $ is replaced by $ 2 $ AND $ 2 = 2 $ and $ 3 $ is replaced with $ 3 $ AND $ 2 = 2 $ . The set of numbers is $ \{1, 2, 4, 5\} $ . - For the second query, there are $ 3 $ distinct numbers between $ 2 $ and $ 5 $ : $ 2 $ , $ 4 $ , and $ 5 $ . - For the third query, $ 2 $ is replaced by $ 2 $ XOR $ 3 = 1 $ , $ 4 $ is replaced by $ 4 $ XOR $ 3 = 7 $ , and $ 5 $ is replaced by $ 5 $ XOR $ 3 = 6 $ . The set of numbers is $ \{1, 6, 7\} $ . - For the fourth query, there are $ 2 $ distinct numbers between $ 1 $ and $ 6 $ : $ 1 $ and $ 6 $ . - For the fifth query, $ 1 $ is replaced by $ 1 $ OR $ 8 = 9 $ . The set of numbers is $ \{6, 7, 9\} $ . - For the sixth query, there is one distinct number between $ 8 $ and $ 10 $ : $ 9 $ .