Sonya and Bitwise OR
Contest: Codeforces Round 495 (Div. 2)
Difficulty rating: 2600
Tags: bitmasks, data structures, divide and conquer

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

Input format:
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$$$.

Output format:
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$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

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

Example input:
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

Example output:
5
1
7
4
1
4

Example input:
5 5 7
6 0 3 15 2
2 1 5
1 4 4
2 1 5
2 3 5
2 1 4

Example output:
9
7
2
4

Editorial:
Will be added soon.