[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\) 。

• 样例输入

• 样例输出

• 数据范围与提示

对于 \(20\%\) 的数据，\(n,m \le 500\)，所有数字不超过 \(2^9\) ​​。

对于 \(50\%\) 的数据，\(n,m \le 1000\) 。

对于 \(100\%\) 的数据，\(n,m \le {10}^6\)​​，所有数字不超过 \(2^{30}\) ​​。

 

 

YZOJ P4263

---

 

 

 

作为一道合格的签到题，很懊悔没有在考场上切掉它。明明已经想到了正解

直接暴力 \(20pts\) 不用多说。

对于这类问题，最常见的方法就是把这些数二进制分解，然后讨论每一位上的情况。要使整串序列非严格单调递增，就是要让 \(\forall i \in [1,n-1], a_i \leq a_{i+1}\) 。

对于本题，很显然的一个贪心就是：从高位到低位找到相邻两个数 \(i\) 和 \(i+1\) 的第一个不同的二进制位设为 \(d\)，如果 \(d_{i}=0, d_{i+1}=1\) 那么选择 \(0\) 不反转，如果 \(d_{i}=1, d_{i+1}=0\) 那么选择 \(1\) 反转。同时相等的位选什么都可以，但是为了使 \(x\) 最小应优先选 \(0\) 。

所以对于每个二进制位统计一下有几对相邻的 \(a\) 必须选 \(0\) 或 \(1\)，那么修改就是 \(O(loga)\) 的。对于每个询问都 \(O(loga)\) 统计一下哪些位必须选 \(1\) ，并加入 \(x\) 中，注意如果出现必须同时选 \(0\) 和 \(1\) 的情况那就是无解了。

时间复杂度 \(O((n+q)loga)\) 。