CF1936D Bitwise Paradox

给定两个长度为 $n$ 的数组 $a$ 和 $b$，以及一个固定整数 $v$。 一个区间 $[l, r]$ 被称为好区间，当且仅当 $b_l \mid b_{l+1} \mid \ldots \mid b_r \ge v$，其中 $|$ 表示[按位或运算](https://en.wikipedia.org/wiki/Bitwise_operation#OR)。一个好区间的美丽值定义为 $\max(a_l, a_{l+1}, \ldots, a_r)$。 你需要处理 $q$ 个两种类型的操作： - “1 i x”：将 $b_i$ 赋值为 $x$； - “2 l r”：在所有满足 $l \le l_0 \le r_0 \le r$ 的好区间 $[l_0, r_0]$ 中，求最小的美丽值。如果不存在好区间，则输出 $-1$。 请处理所有操作。

每组测试数据包含多组测试用例。第一行包含测试用例组数 $t$（$1 \le t \le 10^5$）。每组测试用例描述如下。 每组测试用例的第一行包含两个整数 $n$ 和 $v$（$1 \le n \le 2 \cdot 10^5$，$1 \le v \le 10^9$）。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$）。 第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$1 \le b_i \le 10^9$）。 第四行包含一个整数 $q$（$1 \le q \le 2 \cdot 10^5$）。 接下来的 $q$ 行，每行描述一个操作，格式如下： - “1 i x” （$1 \le i \le n$，$1 \le x \le 10^9$）； - “2 l r” （$1 \le l \le r \le n$）。 保证所有测试用例中 $n$ 的总和与 $q$ 的总和均不超过 $2 \cdot 10^5$。

对于每组测试用例，输出所有类型为 2 的操作的答案。

在第一个测试用例中，$a = [2, 1, 3]$，$b = [2, 2, 3]$，$v = 7$。 第一个操作为类型 2，$l = 1$，$r = 3$。可用的最大区间为 $[1, 3]$，其按位或为 $b_1 \mid b_2 \mid b_3 = 3$，小于 $v$，因此不存在好区间。 第二个操作将 $b_2$ 改为 $5$，此时 $b = [2, 5, 3]$。 第三个操作为类型 2，$l = 2$，$r = 3$。可选区间为 $[2, 2]$、$[3, 3]$、$[2, 3]$。其中 $b_2 = 5 < v$，$b_3 = 3 < v$，只有最后一个区间 $b_2 \mid b_3 = 7$，是好区间，其美丽值为 $\max(a_2, a_3) = 3$。 第四个操作为类型 2，$l = 1$，$r = 3$。好区间为 $[1, 2]$、$[2, 3]$、$[1, 3]$，它们的美丽值分别为 $2$、$3$、$3$，因此答案为 $2$。 在第二个测试用例中，$a = [5, 1, 2, 4]$，$b = [4, 2, 3, 3]$，$v = 5$。 第一个操作为 $l = 1$，$r = 4$。唯一的好区间为 $[1, 2]$、$[1, 3]$、$[1, 4]$，它们的美丽值均为 $5$，因此答案为 $5$。 由 ChatGPT 4.1 翻译