幻想之终结（题解）

旅行者们，相信你们在幻想乡玩的还算开心吧，如果你们还想再次来访，请看入坑指南*****************************

恭喜 Sugar Ak 比赛，以下是前五：

1. Sugar

2. John_zyj

3. 黄家祥

4. AnotherTransition

5. __baozii__

然后到我们的题解环节：

A 红魔塔

题意 : 给你三个数 ，塔高在接下来 天内每天会增加 ，但是不能超过 ，请你求出塔高最终会是多少。

观察到最终的答案一定是 和 中的最小值，判断并输出即可。 时间复杂度

B 冰冻青蛙

题意 ：略。

要想构造一个排列使得冰冻所有的青蛙，冰冻的青蛙编号必须得满足 ，不妨观察 为哪些数时，满足该条件。我们可以最直观地发现一个因数 .对于一个长度为 的排列,一定存在 个编号为倍数的青蛙个数，全部放在 的位置上，使冰冻一只青蛙的贡献是 （左、中、右）因此可以冰冻 个青蛙，剩下 个青蛙没被冻结。所以:

• 当 比较小时， 是 的整数倍数时有解，反之无解。

• 当 够大时，处理多余的青蛙，只需要找到最小的 且 且 处理一下就行。

综上所述，其实我们可以跑一遍循环把所有 的数存到一个栈或队列里，在构造时，优先从里面取数构造 位置以及最后一个位置来符合条件，最后把所有其它的数构造一下就行。

C 灵梦的字符串问题

题意 ：略。

对于一个字符串 的某个字符 ，它能够使得字典序变小当且仅当它后面第一个和它不同的字符比它大。所以可以预处理出每个字符复制之后是否能让整个串字典序变小。

对于一个字符串，由于字典序是先由前面元素决定，于是我们应当首先让位置靠前的可以使字典序变小的位置被复制。然后考虑代价，就有从前往后贪心，取字符进行复制，如果目前的总灵力可以取这个位置就取。

D 幽幽子的魔法宴会

题意 : 给你一个数组，你可以选择任意一些位置异或 ，求使数组之和大于等于 的最小

由于存在 我们记以二进制第 位为最高位且这一位为 时，其所有小于他的位之和一定小于这一位的值为  

枚举答案 的第 位为最高位，设当前枚举到第 位作为最高位，我们选择第 位为最高位时，由 ，我们一定会选择所有第位为的所有值，一定不选第 位为 的值，否则一定不优。

这时记选择的这个集合为 ，考虑对于集合 枚举小于 的所有位，如果选择这一位对数组和的贡献大于 ，那么先选上，等选择完所有贡献大于 的位置后，再贪心的删除多余的位置。

现在我们选中了所有可以产生贡献的位置，这是选择第 位作为最高位时我们可以得到的最大贡献，现在我们考虑删除多余的一些贡献来使答案 最小。根据 可知，删掉高位的贡献比删掉所有低位的贡献之和还要更高，所以从高到低枚举每一位，如果删掉这一位数组之和依然大于等于 ，那么删掉这一位是一定最优的做法。 时间复杂度

E 纯粹的退治

题意 ：略。

如果此时序列是 ,灵梦最终的符卡使用次数是 。

对于这个问题的粗略证明：

首先这是次数的下界,因为如果 那么 的符卡总是不能将 减为 .所以至少需要多的 张符卡.

其次,用这个符卡个数可以构造方案:在 新增 个以 为左端点的符卡; 在 时,将 张符卡的右端点设置为 .最后,剩下的符卡都在 停止。

问题变为:

区间如题修改,查询全局 .

设 ,修改就变为

即连续找到首尾相接的两个等长区间,前面的区间 ,后面的区间 .

我们声明这个问题复杂度不低于 ，证明如下：（证明比较长，可跳过）

感谢 edge 哥给出的证明思路.

经典结论:给定初始序列 ,长为 ,进行 次修改区间 和 次查询 的个数,如果能做到总复杂度 ,那么矩阵乘法可以做到 .实际上矩阵乘法 所以这个问题应当至少是 。

证明：略，读者自证不难。

然后将这个问题归约到本题.在序列前面加 个 ,后面加 个 。

首先,可以这个问题可以 让一个前缀 或者 后缀 。

对于一次 +1 操作，就让 进行 ，让 进行 。

对于一次 -1 操作，就让 进行 ，让 进行 。

通过上述操作的组合可以实现 让 +1 或 -1，留作习题。

然后本问题能 统计出全局非负数的个数:对于 ，答案的增量就是全局非负数的个数.

所以本问题能 统计出 的个数，先求一遍 的数的个数,然后全局 -1 ,求出 的数的个数,由 求得。

（证毕）

通过分块可以做到 .

对于一个修改

• 散块暴力统计答案.
• 对于整块,记录 表示整体偏移量, 表示块中非负数的个数, 表示 的答案.记录一个数据结构 能够查值是 的数的个数
• 对于整块 +1,,然后用 更新 的值,更新 .
• 对于整块 -1,然后用 更新 的值,,更新 .
• 查询每个块的答案加起来

的选择:

• unordered_map 会TLE
• 手写哈希(线性探测或者平方探测) 会过
• 使用数组(发现有用的值比较小 ) 会过得很快
• 排序后进行二分,复杂度会乘

另解 ：

使用更强大的数据结构,允许找到每个块 数得个数(本问题中 ),使用分散层叠算法,可以做到 (edge 提供)

另解 ：

对询问进行根号重构，在一块询问里将修改端点离散化，然后扫描询问。对于每个询问在离散化之后的区间进行答案统计，使用一些桶。(fallleaves01 提供)

验题人题解：

对于给出的序列，选择任意区间减 使得所有数变成 的最小操作次数，容易发现实际上就是求 。

我们令 ，也就是求 为正数的和。

我们考虑修改操作会对 产生什么影响，容易发现，该操作即为对（操作1） 减去 ，对 （操作2） 加上 ，因此该题就变成了维护序列 的正数和，并能够实现区间 区间 。

对于区间操作，我们可以使用分块，然后我们考虑上面两个操作对正数和的影响

操作1：对于区间 对正数和的影响，即为考虑区间内正数的数量，答案就会变成 ，其中 代表区间内正数的数量

操作2：对于区间 对正数和的影响，即考虑区间内正数与 的数量，答案就会变成 ，其中 代表区间内正数与 的总数量

但是由于区间会整个 与 ，我们令整个区间 与 的和称为偏差量 ，并给这个块建个桶并求前缀和 ，记整个区间的大小为

那么如果要求整个块多次 或 之后正数的数量，就求 即可，其中 代表小于等于 的数量，在经过 的偏差后，变成了小于等于 的数量，用整个区间减去就变成了正数的数量，同理 就为正数与 的总数量

但是由于数据范围，我们肯定无法将桶建完整，并且整个区间只会 与 因此我们的桶可以建得小一点，我们假设该区间大小为阈值 ，能处理 的偏差，在 时，我们重新统计该块，将 重新置为

考虑复杂度，每次操作都要对两边不完整的块重新统计，复杂度为

遍历块

对 的块重新统计，考虑到每次至多偏差 ，因此一个块最大的重新统计的频率为 ，复杂度为

整合一下即为 ，当 时，即为 足以通过此题 （但是考虑到区间可能不会太大，并且会 与 抵消，因此实际上 取 左右效果较好）

出题人安全声明：本题时间开到了标程的 倍。

F 斯卡雷特家的游戏

题意 ：略。

称 Remilia 为 Alice，Flandre 为 Bob。

对于只有一堆石子的情况进行特判，一定胜。

对于至少两堆石子的情况：

结论：石子中有大小为 的堆是那么先手必败的充要条件。

归纳证明：

首先，对于石子堆数归纳，其次对于石子个数归纳。

对于有两堆石子的情况：如果有 那么 Bob 让 Alice 取这堆，转移到先手胜的情况，Alice 败。否则 Alice 可以取到剩余 ，转换到先手败的情况，Alice 胜

对于大于两堆石子的情况：

如果有 ：

如果全是 的堆，Bob给 个给 Alice 取，转移到自己胜的情况。

如果有大小大于 的堆和大小为 的堆，那么 Bob 将所有大小为 的堆都给 Alice，让她取完，由归纳假设，转移到了自己胜的情况。

所以 Alice 必败。

如果无 ：

那么无论 Bob 怎么给 Alice 选，Alice 都可以取到一个 ，转移到 Bob 必败，所以 Alice 胜。

结语

各位读者们，我们有缘再会。

「幻想郷の風は、私をどこへでも連れて行ける」

「さようなら、幻想郷。また、不思議の縁に会おう。」