CF1936D.Bitwise Paradox

You are given two arrays $a$ and $b$ of size $n$ along with a fixed integer $v$.

An interval $[l, r]$ is called a good interval if $(b_l \mid b_{l+1} \mid \ldots \mid b_r) \ge v$, where $|$ denotes the bitwise OR operation. The beauty of a good interval is defined as $\max(a_l, a_{l+1}, \ldots, a_r)$.

You are given $q$ queries of two types:

• "1 i x": assign $b_i := x$;
• "2 l r": find the minimum beauty among all good intervals $[l_0,r_0]$ satisfying $l \le l_0 \le r_0 \le r$. If there is no suitable good interval, output $-1$ instead.

Please process all queries.

给你两个长度为 $n$ 的数组 $a$ 和 $b$，以及一个固定整数 $v$。

若区间 $[l, r]$ 满足 $(b_l \mid b_{l+1} \mid \ldots \mid b_r) \ge v$，则称其为好区间，其中 $|$ 表示按位或运算。一个好区间的美丽值定义为 $\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$。

请处理全部查询。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $v$ ($1 \le n \le 2 \cdot 10^5$, $1 \le v \le 10^9$).

The second line of each testcase contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$).

The third line of each testcase contains $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le 10^9$).

The fourth line of each testcase contains one integer $q$ ($1 \le q \le 2 \cdot 10^5$).

The $i$-th of the following $q$ lines contains the description of queries. Each line is of one of two types:

• "1 i x" ($1 \le i \le n$, $1 \le x \le 10^9)$;
• "2 l r" ($1 \le l \le r \le n$).

It is guaranteed that both the sum of $n$ and the sum of $q$ over all test cases do not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$ 行中，第 $i$ 行描述一个查询，每行属于以下两种类型之一：

• “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$。

For each test case, output the answers for all queries of the second type.

对于每个测试用例，输出所有第二类查询的答案。

In the first test case, $a = [2, 1, 3]$, $b = [2, 2, 3]$, and $v = 7$.

The first query is of the second type and has $l = 1$ and $r = 3$. The largest interval available is $[1, 3]$, and its bitwise OR is $b_1 \mid b_2 \mid b_3 = 3$ which is less than $v$. Thus, no good interval exists.

The second query asks to change $b_2$ to $5$, so $b$ becomes $[2, 5, 3]$.

The third query is of the second type and has $l = 2$ and $r = 3$. There are three possible intervals: $[2, 2]$, $[3, 3]$, and $[2, 3]$. However, $b_2 = 5 \lt v$, $b_3 = 3 \lt v$. So only the last interval is good: it has $b_2 \mid b_3 = 7$. The answer is thus $\max(a_2, a_3) = 3$.

The fourth query is of the second type and has $l = 1$ and $r = 3$. There are three good intervals: $[1, 2]$, $[2, 3]$, and $[1, 3]$. Their beauty is $2$, $3$, $3$ correspondingly. The answer is thus $2$.

In the second test case, $a = [5, 1, 2, 4]$, $b = [4, 2, 3, 3]$, and $v = 5$.

The first query has $l = 1$ and $r = 4$. The only good intervals are: $[1, 2]$, $[1, 3]$, $[1, 4]$. Their beauty is $5$, $5$, $5$ correspondingly. The answer is thus $5$.

在第一个测试用例中，$a = [2, 1, 3]$，$b = [2, 2, 3]$，且 $v = 7$。

第一个查询为第二类查询，参数为 $l = 1$ 和 $r = 3$。当前可选的最大区间为 $[1, 3]$，其按位或值为 $b_1 \mid b_2 \mid b_3 = 3$，小于 $v$。因此，不存在好区间。

第二个查询要求将 $b_2$ 修改为 $5$，于是 $b$ 变为 $[2, 5, 3]$。

第三个查询为第二类查询，参数为 $l = 2$ 和 $r = 3$。共有三个可能的区间：$[2, 2]$、$[3, 3]$ 和 $[2, 3]$。但 $b_2 = 5 \lt v$，$b_3 = 3 \lt v$，因此仅最后一个区间是好区间：其按位或值为 $b_2 \mid b_3 = 7$。答案即为 $\max(a_2, a_3) = 3$。

第四个查询为第二类查询，参数为 $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$。