Sonya and Bitwise OR
题意翻译
有一个长度为 $n$ 的数组 $a_{1 \sim n}$ ,有 $m$ 次操作,操作分两类:
1. 将 $a_i$ 修改成 $y$ ;
2. 给定 $l$ 和 $r$ ,询问有多少个区间 $[L, R]$ 满足 $l \le L \le R \le r$ 且 $a_{L \sim R}$ 按位或和至少为 $x$ 。(即: $a_L \text{ or } a_{L + 1} \text{ or } \cdots \text{ or } a_R \ge x$ )
其中 $x$ 是一开始给定的一个整数。
$1 \le n, m \le 10^5$ ; $0 \le a_i, x, y < 2^{20}$ 。
Translated by @OrangeLee
题目描述
Sonya has an array $ a_1, a_2, \ldots, a_n $ consisting of $ n $ integers and also one non-negative integer $ x $ . She has to perform $ m $ queries of two types:
- $ 1 $ $ i $ $ y $ : replace $ i $ -th element by value $ y $ , i.e. to perform an operation $ a_{i} $ := $ y $ ;
- $ 2 $ $ l $ $ r $ : find the number of pairs ( $ L $ , $ R $ ) that $ l\leq L\leq R\leq r $ and bitwise OR of all integers in the range $ [L, R] $ is at least $ x $ (note that $ x $ is a constant for all queries).
Can you help Sonya perform all her queries?
Bitwise OR is a binary operation on a pair of non-negative integers. To calculate the bitwise OR of two numbers, you need to write both numbers in binary notation. The result is a number, in binary, which contains a one in each digit if there is a one in the binary notation of at least one of the two numbers. For example, $ 10 $ OR $ 19 $ = $ 1010_2 $ OR $ 10011_2 $ = $ 11011_2 $ = $ 27 $ .
输入输出格式
输入格式
The first line contains three integers $ n $ , $ m $ , and $ x $ ( $ 1\leq n, m\leq 10^5 $ , $ 0\leq x<2^{20} $ ) — the number of numbers, the number of queries, and the constant for all queries.
The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0\leq a_i<2^{20} $ ) — numbers of the array.
The following $ m $ lines each describe an query. A line has one of the following formats:
- $ 1 $ $ i $ $ y $ ( $ 1\leq i\leq n $ , $ 0\leq y<2^{20} $ ), meaning that you have to replace $ a_{i} $ by $ y $ ;
- $ 2 $ $ l $ $ r $ ( $ 1\leq l\leq r\leq n $ ), meaning that you have to find the number of subarrays on the segment from $ l $ to $ r $ that the bitwise OR of all numbers there is at least $ x $ .
输出格式
For each query of type 2, print the number of subarrays such that the bitwise OR of all the numbers in the range is at least $ x $ .
输入输出样例
输入样例 #1
4 8 7
0 3 6 1
2 1 4
2 3 4
1 1 7
2 1 4
2 1 3
2 1 1
1 3 0
2 1 4
输出样例 #1
5
1
7
4
1
4
输入样例 #2
5 5 7
6 0 3 15 2
2 1 5
1 4 4
2 1 5
2 3 5
2 1 4
输出样例 #2
9
7
2
4
说明
In the first example, there are an array \[ $ 0 $ , $ 3 $ , $ 6 $ , $ 1 $ \] and queries:
1. on the segment \[ $ 1\ldots4 $ \], you can choose pairs ( $ 1 $ , $ 3 $ ), ( $ 1 $ , $ 4 $ ), ( $ 2 $ , $ 3 $ ), ( $ 2 $ , $ 4 $ ), and ( $ 3 $ , $ 4 $ );
2. on the segment \[ $ 3\ldots4 $ \], you can choose pair ( $ 3 $ , $ 4 $ );
3. the first number is being replacing by $ 7 $ , after this operation, the array will consist of \[ $ 7 $ , $ 3 $ , $ 6 $ , $ 1 $ \];
4. on the segment \[ $ 1\ldots4 $ \], you can choose pairs ( $ 1 $ , $ 1 $ ), ( $ 1 $ , $ 2 $ ), ( $ 1 $ , $ 3 $ ), ( $ 1 $ , $ 4 $ ), ( $ 2 $ , $ 3 $ ), ( $ 2 $ , $ 4 $ ), and ( $ 3 $ , $ 4 $ );
5. on the segment \[ $ 1\ldots3 $ \], you can choose pairs ( $ 1 $ , $ 1 $ ), ( $ 1 $ , $ 2 $ ), ( $ 1 $ , $ 3 $ ), and ( $ 2 $ , $ 3 $ );
6. on the segment \[ $ 1\ldots1 $ \], you can choose pair ( $ 1 $ , $ 1 $ );
7. the third number is being replacing by $ 0 $ , after this operation, the array will consist of \[ $ 7 $ , $ 3 $ , $ 0 $ , $ 1 $ \];
8. on the segment \[ $ 1\ldots4 $ \], you can choose pairs ( $ 1 $ , $ 1 $ ), ( $ 1 $ , $ 2 $ ), ( $ 1 $ , $ 3 $ ), and ( $ 1 $ , $ 4 $ ).
In the second example, there are an array \[ $ 6 $ , $ 0 $ , $ 3 $ , $ 15 $ , $ 2 $ \] are queries:
1. on the segment \[ $ 1\ldots5 $ \], you can choose pairs ( $ 1 $ , $ 3 $ ), ( $ 1 $ , $ 4 $ ), ( $ 1 $ , $ 5 $ ), ( $ 2 $ , $ 4 $ ), ( $ 2 $ , $ 5 $ ), ( $ 3 $ , $ 4 $ ), ( $ 3 $ , $ 5 $ ), ( $ 4 $ , $ 4 $ ), and ( $ 4 $ , $ 5 $ );
2. the fourth number is being replacing by $ 4 $ , after this operation, the array will consist of \[ $ 6 $ , $ 0 $ , $ 3 $ , $ 4 $ , $ 2 $ \];
3. on the segment \[ $ 1\ldots5 $ \], you can choose pairs ( $ 1 $ , $ 3 $ ), ( $ 1 $ , $ 4 $ ), ( $ 1 $ , $ 5 $ ), ( $ 2 $ , $ 4 $ ), ( $ 2 $ , $ 5 $ ), ( $ 3 $ , $ 4 $ ), and ( $ 3 $ , $ 5 $ );
4. on the segment \[ $ 3\ldots5 $ \], you can choose pairs ( $ 3 $ , $ 4 $ ) and ( $ 3 $ , $ 5 $ );
5. on the segment \[ $ 1\ldots4 $ \], you can choose pairs ( $ 1 $ , $ 3 $ ), ( $ 1 $ , $ 4 $ ), ( $ 2 $ , $ 4 $ ), and ( $ 3 $ , $ 4 $ ).