AGC006

快乐翻题解(sqrt{})

A Prefix and Suffix

这一场我怎么一道都不会啊/kk

我咋这都不会啊/dk

直接按题解构造（大雾

显然(X=1)或(2n-1)没有答案

如果一层(a[1-(2N-1)])中(a[N]=a[N+1](a[N-1]))那么最后的值一定是(a[N])

那么让第二层中间两个取到(X)就好了(color{white}{ ext{，这显然可以做到}})。

出题人：如果你知道这些trick你就是在做A+B，否则你100%不会

设(f_i)表示(i)期望，初始是(a)

一次操作是让(f_i=0.5(2f_{i-1}+2f_{i+1})-f_i=f_{i-1}+f_{i+1}-f_i)

然后有(K)轮操作，你还是不会（Orzyyb）

差分(f)，设为(d)。考虑操作对(d)的影响。

(newd_i=(f_{i+1}+f_{i-1}-f_i)-f_{i-1}=f_{i+1}-f_i=oldd_{i+1})

(newd_{i+1}=f_{i+1}-(f_{i+1}+f_{i-1}-f_i)=f_i-f_{i-1}=oldd_i)

所以一次操作就是交换相邻的(d)值，这个倍增一下就能做了。

显然要二分。。。然后就不会了

还是要用到上面的性质，如果正中间出现相同的那么最后就是那一个，如果没有怎么办。。。

如果没有说明中间一定形如0 1 0或者1 0 1，你可以继续扩展，看偏离一点的相邻两位是否相同，如果相同就是那个。

（可以拿个图画一下）

如果相邻全是不同的特判一下。

先有一堆结论，

一列的3个数肯定在一起（而且按照升序或降序排）

不管怎么转一列肯定和原来奇偶性相同（分组一下）

现在一列看成一个数，升序和降序看成一种状态（符号）

一个操作就是交换两个位置差为2的数，并把这3个数×-1

分组完了一次操作会变成：交换一个组里的两列并×-1，在另一个组里同位置×-1

到这里还是不会，最后一个神仙操作：一定可以给同组两个相邻的数×-1，不影响其它位置（具体看题解给了方法）

然后限制变成了：A组的交换次数与B组取反次数同奇偶、B组的交换次数与A组取反次数同奇偶