AGC006D
非常有意思的一个题。
直接做复杂度是 $O(n^2)$ 的而且看不出什么优化空间。
“中位数”的题往往和二分答案有关，因为这样可以转化成区间内 $0/1$ 的个数。这个题，可以先二分答案，设二分出来的值是 $x$ ，我们尝试判断第一层的数是否 $\le x$ 。我们把所有 $\le x$ 的数设置为 $0$ ，把剩下的数设置为 $1$ 。不难发现这个序列在进行操作后得到的序列的 $01$ 含义是不变的。现在我们转化成了一个 $01$ 序列进行操作，最后堆顶的数是 $0$ 还是 $1$ 。
然后画个图手玩一下，会发现所有长度 $\ge 2$ 的连续段在往上的过程中必然会复读，而长度为 $1$ 的连续段必然会翻转。而在 $\ge 2$ 的连续段复读的过程中会和附近翻转的 $01$ 变得相同。而且，一个长度不少于 $2$ 的连续段一定会一直向左同化，直到遇到一个同样长度不小于 $2$ 的连续段。
现在问题就变得很简单了。考虑最中间这个格子最早会被谁同化，就是枚举它左边和右边看看第一个长度大于等于 $2$ 的连续段的距离。如果不会被同化，也就是说相邻互不相同，那么这个东西就会一直反色直到结束。
复杂度 $O(n\log n)$ 。
AGC006C
去年写的题。
大概就是考虑跳跃之后期望的变化，大概是个形如 $a_i = a_{i+1}+a_{i-1}-a_i$ 的东西。这是个经典的差分形式，差分后就是交换 $d_i,d_i+1$ 。于是现在问题就变成了给一个置换，求 $10^{18}$ 次后的序列长啥样，经典的快速幂。
AGC006E
一个感觉很可做的 E 。
首先，任意一列内部的三个数自始至终不会变，只会改变上下的顺序。所以我们给每列标号为最小数除以 $3$ 上取整，如果这列是颠倒的就标为负数，例如 $1,2,3$ 标为 $1$ ，$9,8,7$ 标为 $-3$ 。
于是现在我们相当于给定一个数组有正负，每次可以交换一对距离为 $2$ 的数同时给这两个数以及中间的数一起取反，最后需要变成 $1,2,3,\dots ,n$ 。
显然，我们应当对奇偶分开考虑，交换只会发生在奇数内部和偶数内部。
手玩一下五个数或七个数的情况，会发现当我们交换了 $i,j$ ，如果 $i,j$ 都是奇数，那么当 $|i-j| \equiv 1 \pmod 2$ 的时候这两个数会同时变号，并且可以任意选择一个 $[i,j]$ 内部的偶数位置变号。具体操作就是假定要变号的位置是 $k$ ，就先 $i \to k-1$ 再 $j \to k+1$ 然后交换 $i,j$ 再移动回去。
于是会发现一个奇妙的操作：可以让 $i,j$ 先操作一次再操作一次。于是我们可以让奇数或者偶数中的两个位置变换符号！
所以说，我们只需要关心奇数和偶数内部的负号的奇偶性。
由于这个操作的作用顺序是不重要的，我们可以先将上下分别通过交换排序，再通过这种操作来消去符号，也就是看奇数偶数内部的负号个数是否为奇数，若有一边为奇数就不行。所以现在对于交换操作，交换时 $i,j$ 得到的负号就没用了，只有另一边的负号有用。
现在还有一个问题在于如何排序来使上下尽量都是偶数。但是手玩一下发现，排序的时候交换次数的奇偶性是一定的。因为每次交换除了交换的两个元素中间的逆序对改变个数一定是 $2,-2$ 这种，所以交换次数的奇偶性就是逆序对的奇偶性。这个题中可以随便排序，每次把 $1,2,3,\dots ,n$ 归位或者按照置换来最少次数排序都一样的。
AGC006F
神仙题。
开始一看以为是什么三元环计数之类的，做了一下发现不太可做。因为这个东西会一直不断加边就很困难。没想到最后还是个结论题。。
考虑给整个图染色，染 $A,B,C$ 三种颜色。
然后结论：
如果染色结束了，我们并没有用到全部的三种颜色。
这是最显然的情况。图上根本不存在 $x \to y , y \to z$ ，自然不存在加边，所以边数保持不变。
如果染色结束了，我们用到了全部的三种颜色，并且没有出现矛盾。
结论是，任意两个 $A,B$ 点间，任意两个 $B,C$ 点间，任意两个 $C,A$ 点间都会连上边。
考虑三个点 $x,y,z$ 分别的颜色是 $A,B,C$。考虑一个点 $v$ 与 $x,y,z$ 中任意一个相邻（这里的相邻是无向图上的）。显然我们必然可以通过连边，让 $v$ 与这三个点中的两个点相邻。然后再对于一个点 $w$ ，假定它和 $v,x,y,z$ 中有一个相邻，那么我们必然可以通过连边，让它与其中至少两个相邻。然后我们不管 $v$ ，就可以说明它和 $x,y,z$ 中至少有一个相邻。归纳下去，我们可以说明 $w$ 与其中两个点相邻。同理，我们可以说明连通块内任意一个点和其中两个点相邻。
如果这张图不能用这三个颜色染色。这个时候整个连通块在一直操作下去后会变成一个完全图（包括自环的完全图）。
手玩过都会发现，只要有自环，这个连通块必然就被整成完全图了。
考虑发生冲突的一条边。它肯定在无向图的某个环上。如果不在，它是个桥，那么通过合理分配颜色它一定不会有冲突。考虑这个无向图的环，每次选择这个环上的 $x \to y , y \to z$ 这么两条边，如果不存在这样两个边，那么一定不会有冲突存在，然后整成 $x \to z$ ，然后这个环就会缩小，同时这个环仍然不能满足限制，因为会发现无论不满足限制的边是否被缩，这个环还是不满足限制的。一直这么进行下去，最后一定会得到一元环。