loj#P2767. 「ROI 2017 Day 1」排序幻觉

「ROI 2017 Day 1」排序幻觉

题目描述

题目译自 ROI 2017 Day 1 T2. Иллюзия сортировки

给一个数组 a[1],a[2],,a[n]a[1], a[2], \ldots, a[n],选择一个数 bb,如果 bb 满足

(a[1]b)(a[2]b)...(a[n]b)(a[1] ⊕ b) ≤ (a[2] ⊕ b) ≤ . . . ≤ (a[n] ⊕ b)

则称 bb 是数组 aa 的幻数。此处 表示按位异或。
该数组将会被先后修改 qq 次,我们每次只修改一个数。
第一次修改前以及每次修改后,请给出当前数组最小的幻数,如果当前数组不存在幻数请输出 1-1

输入格式

第一行有一个整数 nn
第二行有 nn 个整数,表示数组 aa
第三行有一个整数 qq
在接下来的 qq 行中,每行有两个整数 pi,vip_i, v_i,表示将 a[pi]a[p_i] 修改为 viv_i

输出格式

(q+1)(q+1) 行,每行一个整数,表示当前数组最小的幻数。

3
0 1 4
3
2 7
3 3
1 4
0
2
-1
4

数据范围与提示

子任务 分值 nn qq a[i],via[i], v_i
1 30 1n5001⩽n⩽500 0q5000⩽q⩽500 0a[i],vi290 ⩽ a[i], v_i ⩽ 2^9
2 29 1n10001⩽n⩽1000 0q10000⩽q⩽1000 0a[i],vi2300 ⩽ a[i], v_i ⩽ 2^{30}
3 21 1n1051⩽n⩽10^5 0q1050⩽q⩽10^5
4 20 1n1061⩽n⩽10^6 0q1060⩽q⩽10^6