题目描述
题目译自 ROI 2017 Day 1 T2. Иллюзия сортировки
给一个数组 a[1],a[2],…,a[n],选择一个数 b,如果 b 满足
(a[1]⊕b)≤(a[2]⊕b)≤...≤(a[n]⊕b)
则称 b 是数组 a 的幻数。此处 ⊕ 表示按位异或。
该数组将会被先后修改 q 次,我们每次只修改一个数。
第一次修改前以及每次修改后,请给出当前数组最小的幻数,如果当前数组不存在幻数请输出 −1。
输入格式
第一行有一个整数 n。
第二行有 n 个整数,表示数组 a。
第三行有一个整数 q。
在接下来的 q 行中,每行有两个整数 pi,vi,表示将 a[pi] 修改为 vi。
输出格式
共 (q+1) 行,每行一个整数,表示当前数组最小的幻数。
3
0 1 4
3
2 7
3 3
1 4
0
2
-1
4
数据范围与提示
子任务 |
分值 |
n |
q |
a[i],vi |
1 |
30 |
1⩽n⩽500 |
0⩽q⩽500 |
0⩽a[i],vi⩽29 |
2 |
29 |
1⩽n⩽1000 |
0⩽q⩽1000 |
0⩽a[i],vi⩽230 |
3 |
21 |
1⩽n⩽105 |
0⩽q⩽105 |
4 |
20 |
1⩽n⩽106 |
0⩽q⩽106 |