CF1004F Sonya and Bitwise OR

Sonya 有一个由 $n$ 个整数构成的数组 $a_1, a_2, \ldots, a_n$，以及一个非负整数 $x$。她需要执行 $m$ 次两种类型的操作： - $1\ i\ y$：将第 $i$ 个元素替换为 $y$，即执行 $a_i := y$； - $2\ l\ r$：在区间 $[l, r]$ 上，统计有多少对 $(L, R)$ 满足 $l \leq L \leq R \leq r$，并且区间 $[L, R]$ 内所有整数的按位或（bitwise OR）结果不少于 $x$（注意，$x$ 对所有查询都是固定的）。 你能帮助 Sonya 完成所有查询吗？ 按位或（bitwise OR）是两个非负整数上的二元运算。计算两个数的按位或时，需要将它们都写成二进制表示。结果是在每一位上，只要两个数中有一个该位为 $1$，结果的该位就为 $1$。例如，$10$ OR $19 = 1010_2$ OR $10011_2 = 11011_2 = 27$。

第一行包含三个整数 $n$、$m$ 和 $x$（$1 \leq n, m \leq 10^5$，$0 \leq x < 2^{20}$）——数组的长度、操作次数和所有查询的常数 $x$。 第二行包含 $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}$），表示将 $a_i$ 替换为 $y$； - $2\ l\ r$（$1 \leq l \leq r \leq n$），表示询问区间 $[l, r]$ 内有多少个子区间，其所有元素的按位或结果不少于 $x$。

对于每个类型为 2 的查询，输出一个整数，表示区间内所有元素按位或不少于 $x$ 的子区间对数。

在第一个样例中，数组为 $[0, 3, 6, 1]$，操作如下： 1. 在区间 $[1, 4]$ 上，可以选择的对有 $(1, 3)$、$(1, 4)$、$(2, 3)$、$(2, 4)$ 和 $(3, 4)$； 2. 在区间 $[3, 4]$ 上，可以选择的对有 $(3, 4)$； 3. 第一个数被替换为 $7$，此时数组变为 $[7, 3, 6, 1]$； 4. 在区间 $[1, 4]$ 上，可以选择的对有 $(1, 1)$、$(1, 2)$、$(1, 3)$、$(1, 4)$、$(2, 3)$、$(2, 4)$ 和 $(3, 4)$； 5. 在区间 $[1, 3]$ 上，可以选择的对有 $(1, 1)$、$(1, 2)$、$(1, 3)$ 和 $(2, 3)$； 6. 在区间 $[1, 1]$ 上，可以选择的对有 $(1, 1)$； 7. 第三个数被替换为 $0$，此时数组变为 $[7, 3, 0, 1]$； 8. 在区间 $[1, 4]$ 上，可以选择的对有 $(1, 1)$、$(1, 2)$、$(1, 3)$ 和 $(1, 4)$。 在第二个样例中，数组为 $[6, 0, 3, 15, 2]$，操作如下： 1. 在区间 $[1, 5]$ 上，可以选择的对有 $(1, 3)$、$(1, 4)$、$(1, 5)$、$(2, 4)$、$(2, 5)$、$(3, 4)$、$(3, 5)$、$(4, 4)$ 和 $(4, 5)$； 2. 第四个数被替换为 $4$，此时数组变为 $[6, 0, 3, 4, 2]$； 3. 在区间 $[1, 5]$ 上，可以选择的对有 $(1, 3)$、$(1, 4)$、$(1, 5)$、$(2, 4)$、$(2, 5)$、$(3, 4)$ 和 $(3, 5)$； 4. 在区间 $[3, 5]$ 上，可以选择的对有 $(3, 4)$ 和 $(3, 5)$； 5. 在区间 $[1, 4]$ 上，可以选择的对有 $(1, 3)$、$(1, 4)$、$(2, 4)$ 和 $(3, 4)$。 由 ChatGPT 4.1 翻译