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](https://en.wikipedia.org/wiki/Bitwise_operation#OR). 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

N/A

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 $ .