Codeforces Round 495 (Div. 2) |
---|
Finished |
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:
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:
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$$$.
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
5
1
7
4
1
4
5 5 7
6 0 3 15 2
2 1 5
1 4 4
2 1 5
2 3 5
2 1 4
9
7
2
4
In the first example, there are an array [$$$0$$$, $$$3$$$, $$$6$$$, $$$1$$$] and queries:
In the second example, there are an array [$$$6$$$, $$$0$$$, $$$3$$$, $$$15$$$, $$$2$$$] are queries:
Name |
---|