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 $ ).