题目简述

        Problem D：给定函数（其中A，B为已知常量），求最小值。

        Problem E：太难简述了。

        Problem F：太难简述了。

        原题目地址：https://atcoder.jp/contests/abc279/tasks

思路

        Problem D：其实我已经翻译得差不多了。可以直接求导得到唯一极值点，由于是整数，所以考虑其附近的整点处的函数值即可。时间复杂度为。注意到函数实际上是一个凸函数，那么为了避免数值误差，可以使用三分法，时间复杂度为。

        Problem E：对于每一个的查询，事实上差别并不大（并且只用考虑元素所处的位置），考虑递推地计算。由于不会进行的交换操作，因此自然地，考虑将所有进行的操作分两大段处理：之前的操作和之后的操作。假设我们从左到右的递推。

        对于之前的操作，从左到右递推是正常操作的顺序，按正常进行即可，相当于维护一个变量，表示当前进行了之前的操作后，元素所处的位置。更新方法为：初值为；当，则更新；当，则更新。这一点直接由交换操作的定义可以得出。

        对于之后的操作，似乎处理起来比较困难。但由于交换位置操作的可逆性，我们可以递推计算。维护数组，表示“之后的操作全部进行后，某元素值所处的位置”（注意，这是一个向量，因为要保存所有元素的位置）。假设我们得到了，如何计算呢？注意到二者唯一的差距就在于操作是否进行；根据的意义，我们可以发现，交换的两个元素，在最后的实际位置其实是（因为是从开始的，所以有这个结论），因此在中只需要交换的位置即可。

        接下来是计算答案。在进行完之前的操作后，问题可以等价地转化为初始序列为，经过之后的操作后，元素所处的位置。由此可以从左到右地维护并顺势计算答案。总的时间复杂度为。

        Problem F：如果熟悉，一下子就能发现这是一个经典的并查集结构：小球之间只需要明确是否归属同一集合。由此我们维护一个关于小球标号的并查集，初始时，每个小球都以自己为根。问题在于如何在这样的并查集中维护小球所属的盒子编号；以及，为了方便修改，如何维护某盒子对应着哪一个集合。

        令数组表示小球所属的盒子编号，数组表示盒子对应的集合的并查集根。如果一个盒子是空的，不妨设。下面分别叙述三个操作：

• 操作3：答案就是。

• 操作2：把对应的集合作为新的根，并更新；注意，这里其实有两种情况，如果，意味着盒子是空的，不需要额外操作。如果，就意味着盒子不空，需要设置一下并查集的数组。

• 操作1：如果，则相当于什么也没干；如果，则需要将所在集合的盒子进行更新：，然后重置根：；如果二者均非空，则需要置。

        上述操作仔细想想也不难明白（如果知道什么是并查集的话）。总的时间复杂度为。

后记

        本场还是没有录像，等我什么时候能做得更好一点再说吧。虽然能很快找准思路，但总是在奇奇怪怪的地方磕磕绊绊。

        代码的github地址：https://github.com/cnzzx/AlgorithmCompetitions。

        我的E题代码有点乱，如有需要，结合题解理解一下吧。