[Ynoi2018]天降之物

本文主要是介绍[Ynoi2018]天降之物，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

天降之物

题解

只有 ** 出题人才会出这种又难调又卡常的 ** 题。

笔者原先很快奶出了一个$O\left(n\sqrt{n}\log n\right)$的做法，然后调了一个下午，交上去后死活过不了，只好又优化了半天优化出了一个$O\left(n\sqrt{n}\right)$，又调了一个晚上，最后还调了半天块长才过。

首先，看到题面题目名我们应该很容易想到分块，当然，这里准确说应该叫根号分治。
对于每个不同的数，我们都维护一个有序数组，我们的修改操作相当于合并两个有序数组。
如果合并的两个数组都小于$S$，直接像归并排序一样用指针合并就行了。
如果合并的两个数组都大于$S$，由于合并是具有永久性的，这种合并当然也是有限的，不会超过$\frac{n}{S}$次，我们也可以像上面那样暴力合并。
但如果我们合并的两个数组一个大于$S$，一个小于$S$呢，这样显然是不能像刚刚那样合并呢。
但是这种一大一小的合并很容易让我们联想到启发式合并，将小的插入到大的里面去。
如何较快地在一个有序数列中插入一个数，明显就是一个$set$的板子嘛。
所以我们可以对每个数都维护一个$set$，前两种操作可以暴力重构$set$，而下面这种就直接将小的$set$一个一个插入到大的里面去即可。

既然是根号分治，我们自然想到需要维护大于$S$的数组之间的答案，由于合并是永久的，我们大于$S$的数组也只会增多，或者被合并，不会凭空消失。
所以，当一个数组变得大于$S$时，我们可以$O\left(n\right)$地将整个序列扫一遍，维护它与其它数组间的答案，这个只需要从左到右一次和从右到左一次，分别记录下距离每个点最近的属于该数组的点即可。
当两个大于$S$的数组合并时，我们只需将它们的答案暴力合并即可。
当一个较小的数组插入到另外一个大于$S$数组里面去时，我们同样可以对于插入的每一个点维护它与其它数字的距离。
由于每一个数只会插入到一个大于$S$的数组一次，所以每个数自然也只会维护一次。
同样，如果求答案时是两个大于$S$的数组，我们直接将我们记录的答案输出即可，如果存在小于$S$的数组，我们可以就对于这个小数组的每个数看看它与另外一个的距离。

至于维护序列中的每个数现在应该是什么，我们可以采用并查集。
每次将$x$连到$y$上面后我们都新开一个节点，表示现在值为$x$，先前值为$x$的节点都连到$y$上去了，而之后还会有其它值变成$x$。

容易发现，上面这种做法是时间复杂度是$O(\frac{(n-x)n}{S}+x\frac{n}{S}$

这篇关于[Ynoi2018]天降之物的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---