← 返回题目列表

Codeforces · 1004/F

F. 索尼娅和按位或

中文机器翻译题面 查看原题

Sonya 有一个数组 $$$a_1, a_2, \ldots, a_n$$$,由 $$$n$$$ 整数和一个非负整数 $$$x$$$ 组成。 She has to perform $$$m$$$ queries of two types:

- $$$1$$$ $$$i$$$ $$$y$$$:用值 $$$y$$$ 替换第 $$$i$$$ 个元素,即执行操作 $$$a_{i}$$$ := $$$y$$$;
- $$$2$$$ $$$l$$$ $$$r$$$:找到 $$$l\leq L\leq R\leq r$$$ 和 $$$[L, R]$$$ 范围内所有整数的按位或至少为 $$$x$$$ 的对 ($$$L$$$, $$$R$$$) 的数量(请注意, $$$x$$$ is a constant for all queries).

你能帮助索尼娅完成她所有的查询吗?

按位或是一对非负整数的二元运算。要计算两个数字的按位或,您需要将两个数字都写成二进制表示法。结果是一个二进制数字,如果两个数字中至少有一个的二进制表示法为 1,则该数字的每个数字都包含 1。例如,$$$10$$$ 或 $$$19$$$ = $$$1010_2$$$ 或 $$$10011_2$$$ = $$$11011_2$$$ = $$$27$$$。

输入

第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$x$$$ ($$$1\leq n, m\leq 10^5$$$, $$$0\leq x<2^{20}$$$) - 数字的数量、查询的数量以及所有查询的常量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0\leq a_i<2^{20}$$$) — 数组的数字。

以下 $$$m$$$ 行每行描述一个查询。一行具有以下格式之一:

- $$$1$$$ $$$i$$$ $$$y$$$ ($$$1\leq i\leq n$$$, $$$0\leq y<2^{20}$$$),这意味着你必须用 $$$y$$$ 替换 $$$a_{i}$$$ ;
- $$$2$$$ $$$l$$$ $$$r$$$ ($$$1\leq l\leq r\leq n$$$),这意味着你必须找到从 $$$l$$$ 到 $$$r$$$ 段上所有数字的按位或至少为 $$$x$$$ 的子数组的数量。

输出

对于类型 2 的每个查询,打印子数组的数量,使得范围内所有数字的按位 OR 至少为 $$$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. 在段 [$$$1\ldots4$$$] 上,您可以选择对 ($$$1$$$, $$$3$$$), ($$$1$$$, $$$4$$$), ($$$2$$$, $$$3$$$), ($$$2$$$, $$$4$$$) 和 ($$$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$$$) 和 ($$$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$$$).