本文共 1258 字，大约阅读时间需要 4 分钟。

P3932 浮游大陆的68号岛

$f_i$ 表示前 $i$ 个物品移动到 $i$ 位置的代价 $g_i$ 表示 $i$ 之后的物品移到 $i$ 的代价

这个可以线性预处理 然后就随便搞一下 $O(1)$ 求答案了

P3792 由乃大母神原型和偶像崇拜

这个主要科技就是 $check$ 一个区间的数是否是连续一段的方法

把每个数映射到一个随机数上 然后把区间的数异或起来 看是否等于某连续一段的数对应随机数的异或和

怎么找是哪一段 就是 [ 区间最小值,区间最大值 ]

然后线段树直接搞就行了

P4117 [Ynoi2018] 五彩斑斓的世界

啊啊啊这道题真的好烦好烦好烦好烦

烦死了 我讨厌分块

对序列分块 然后由于块与块没有联系 （哲学上的讲联系具有普遍性，同时也是具体的，这里体现的就是具体性，giao我爱政治）

那么就一个一个块来从头到尾处理 为什么呢 因为一起处理空间不够

此时已经有 $\sqrt{n}$ 个块了 这就要求块内的处理时间大概是 $O(n)$ 的

我们考虑一个科技 在 $O(x)$ 的时间内把块内所有大于 $x$ 的数减小 $x$

用值域个并查集 值相同就在一个并查集中 并维护并查集的大小 和代表的值 将所有值为 $i$ 的数变为值为 $i-x$ 就直接合并查集就行了

若块内最大值是 $m$

• $m\ge 2x$ 将所有小于等于 $x$ 的数加 $x$，整个块打标记减去 $x$ （操作 $x$ 次）
• $m<2x$ 将所有大于 $x$ 的数减去 $x$ （操作 $m-x\le x$ 次）

这就是在 $O(x)$ 的时间内把块内所有大于 $x$ 的数减小 $x$ 的科技了 唯一的缺点就是不能有加、

P5610 [Ynoi2013] 大学

这道题就是让你快速找到区间内某个数的倍数

giaogiaogiao真的很恶心的卡常

直接说科技了 时间太tm难卡了 不得不说毒瘤出题人lxl确实tql

开值域个vector 按顺序保存值是它倍数的下标

找区间的时候在vector上二分

然后删除操作就用一个并查集 记录vector里这个数是否被删除 删除了就指向下一个没被删除的点 就挺暴力挺离谱 但是它很正确

P5072 [Ynoi2015] 盼君勿忘

思路很简单 有个我没见过的操作是处理不同模数下2的幂次

考虑预处理出 $2^1,2^2,2^3$ 和 $2^{\sqrt{n}},2^{2\sqrt{n}},2^{3\sqrt{n}}$ ,这样每个次幂都可以用两个部分直接 乘起来了.