[FJWC2019 Day3] 签到题
时间限制: 1000ms 内存限制:256MB
难度: \(4.5\)
-
题目描述
作为一道签到题,自然只能包含最基本的算法。本题的任务很简单,给定一个长度为 \(n\) 的序列 \(a\),你要将其排序。
由于出题人很菜,不会排序算法,他决定自己编一个。他想找到一个数 \(x\),使得序列中的所有数字都异或上 \(x\) 后序列恰好按从小到大排列。
顺带,这个序列会被进行若干次修改,每次修改后你需要回答当前是否存在一个 \(x\) 满足序列中数字异或上 \(x\) 后按从小到大排列,如果有,请你给出最小的 \(x\) 。
-
输入格式
第一行一个正整数 \(n\) 。
第二行 \(n\) 个非负整数,表示序列 \(a\) 。
第三行一个非负整数 \(q\) ,表示修改次数。
接下来 \(q\) 行,每行一个正整数 \(x\) 和一个非负整数 \(y\),表示将序列中第 \(x\) 个元素修改为 \(y\) 。
-
输出格式
输出 \(q+1\) 行,每行一个整数,第一行表示一开始最小的合法 \(x\) ,之后 \(q\) 行依次表示每次修改后最小的合法 \(x\),如果不存在则这一行输出 \(-1\) 。
-
样例输入
1 2 3 4 5 6 |
3 0 1 4 3 2 7 3 3 1 4 |
-
样例输出
1 2 3 4 |
0 2 -1 4 |
-
数据范围与提示
对于 \(20\%\) 的数据,\(n,m \le 500\),所有数字不超过 \(2^9\) 。
对于 \(50\%\) 的数据,\(n,m \le 1000\) 。
对于 \(100\%\) 的数据,\(n,m \le {10}^6\),所有数字不超过 \(2^{30}\) 。