Bitwise Paradox
Contest: Codeforces Round 930 (Div. 1)
Difficulty rating: 3100
Tags: binary search, bitmasks, data structures, greedy, two pointers

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.

Input format:
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$$$.

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

Constraints:
Time limit: 5.0 s
Memory limit: 1024.0 MB

Note:
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 < v$$$, $$$b_3 = 3 < 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$$$.

Example input:
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

Example output:
-1 3 2 
5 2 2 1 
-1

Editorial:
First we use the line segment tree to maintain sequence $$$b$$$. For the nodes $$$[l,r]$$$ on each line segment tree, we maintain the first and last occurrence positions of each binary bit in the interval.
We need to merge the two intervals, whether it is modification or query. Suppose you want to use the information of $$$[l, mid], [mid +1, r]$$$ to merge the information of $$$[l, r]$$$. Consider the answer that spans two intervals. If we want to make the $$$i-th$$$ position of the interval OR $$$1$$$, then there are two possibilities
1. Select the last occurrence position $$$P$$$ of the $$$i-th$$$ bit in $$$[l,mid].$$$
2. Select the first occurrence position $$$Q$$$ of the $$$i-th$$$ bit in $$$[mid+1,r].$$$
Let $$$x = max(a[P], a[P+1],\ldots, a[mid]), y = max(a[mid + 1], a[mid + 2], \ldots, a[Q]).$$$
If $$$x<=y,$$$ we can choose the position $$$P$$$ greedily, because his price is smaller. If you choose $$$Q,$$$ then you must also choose $$$P,$$$ because choosing $$$P$$$ does not increase max $$$a.$$$ Otherwise, select $$$Q$$$ on the contrary.
With the above greedy, then you can enumerate the first binary bit $$$i$$$ that is larger than $$$v$$$. The $$$i-th$$$ bit of the interval OR must be $$$1$$$, and the $$$i-th$$$ bit of $$$v$$$ is $$$0$$$. For the $$$j-th$$$ $$$(j >i)$$$ bit, if the $$$j-th$$$ bit of $$$v$$$ is $$$1$$$, then the $$$j-th$$$ bit must also be $$$1$$$. The rest of the bits can be regarded as $$$0$$$ or $$$1$$$, you only need to deal with these bits that must be selected $$$1$$$ greedily, and expand the interval.
You can use the st table $$$O(1)$$$ to find the interval max of $$$a$$$, so you can merge the information of the two intervals in the time of $$$O(log V)$$$. With the line segment tree, $$$O(q log n log V + n log V)$$$ can be done.