← 返回题目列表

Codeforces · 1936/D

D. 按位悖论

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

给你两个数组 $$$a$$$ 和 $$$b$$$,大小为 $$$n$$$ 以及一个固定整数 $$$v$$$。

如果 $$$(b_l \mid b_{l+1} \mid \ldots \mid b_r) \ge v$$$ 则称区间 $$$[l, r]$$$ 为良好区间,其中 $$$|$$$ 表示按位 OR 运算。好的区间之美定义为 $$$\max(a_l, a_{l+1}, \ldots, a_r)$$$。

您将获得两种类型的 $$$q$$$ 查询:

- "1 i x": 赋值 $$$b_i := x$$$;
- “2 l r”:在所有好的区间 $$$[l_0,r_0]$$$ 中找到满足 $$$l \le l_0 \le r_0 \le r$$$ 的最小美度。如果没有合适的好区间,则输出$$$-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$$$ 行中的第 $$$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$$$。

输出

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

示例

输入 #1

3
3 7
2 1 3
2 2 3
4
2 1 3
1 2 5
2 2 3
2 1 3
4 5
5 1 2 4
4 2 3 3
6
2 1 4
1 3 15
2 3 4
2 2 4
1 2 13
2 1 4
1 5
6
4
1
2 1 1

输出 #1

-1 3 2 
5 2 2 1 
-1

注意

在第一个测试用例中,$$$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 < v$$$,$$$b_3 = 3 < 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$$$、$$$5$$$。因此答案是$$$5$$$。