（2020-10-7编写）一道有趣的不难的题

没错，这篇文章不是在我学OI时写的，而是在实实在在的2020年写的。这似乎预示着我将不得不重回竞赛的怀抱了，祝我好运吧。

题目大意： 对一个长为$n$的数列$\{a_n\}$，有以下两个操作： $1.$求和操作：数列$\{a_1,a_2,...,a_n\}$变为$\{a_1,a_1+a_2,...,a_1+a_2+...+a_n\}$； $2.$翻转操作：数列$\{a_1,a_2,...,a_n\}$变为$\{a_n,a_{n-1},...,a_1\}$。 给定两个长为$n$的数列$\{a_n\}$和$\{b_n\}$，问能不能对$\{a_n\}$进行有限次数的上述操作，使得整个数列各项和$\{b_n\}$中的各项对应相等。如果能，输出最小操作次数，否则，输出$-1$。 你需要在$1s$内解决$T$组数据。 数据范围：$T\le 20,n\le 10^5,1\le a_1,...,a_n,b_1,...,b_n\le 10^{12}$。

做法： 本题是一道思维题。 注意到一开始数列中的项都是正整数，因此在进行一次求和操作后，整个数列必定是单调递增的。算上翻转操作，我们可以断定，只要进行过一次求和操作，则整个数列要么单调递增，要么单调递减。而连续进行两次翻转操作就和没翻转一样，所以最优的操作方法一定是求若干次和，然后翻转一次，然后继续往下，这样。 我们发现两种操作都是可逆的，也就是说，如果我们知道一个数列$\{a_n\}$经过一次求和或翻转后，得到一个数列$\{b_n\}$，而$\{b_n\}$已知，我们可以用$O(n)$的时间求得$\{a_n\}$，且很显然，$\{a_n\}$是唯一的。那么与其正着算，还不如从目标序列$\{b_n\}$一步步倒回去，看它会不会在某个时刻和$\{a_n\}$相等。 如果$\{b_n\}$单调递减，则它的前一步一定不是求和（因为求和操作后得到的数列必然是单调递增的），所以前一步只能是翻转，于是将它翻转过来，操作次数$+1$； 如果$\{b_n\}$单调递增，则它的前一步可以是求和，也可以是翻转，但如果前一步是翻转，那么再前一步一定也是翻转（因为翻转一次后数列单调递减），前面说过连续翻转两次没有意义，因此有意义的前一步必然是求和，这时就对数列求一个差分（求前缀和的逆操作），操作次数$+1$； 这样循环下去，中间一直判断得到的每一个数列是否与$\{a_n\}$相等，如果相等就立刻退出，输出操作次数即可。如果某个时刻$\{b_n\}$不单调了，那它要么就和$\{a_n\}$相等，要么就翻转一次后，和$\{a_n\}$相等，否则，我们就能得出无解的结论，输出$-1$。 这是一个可行的算法，那么它的时间复杂度如何呢？注意到连续多次求前缀和，数列中最大项的大小是指数级增长的，而目标序列中最大项也不会超过$10^{12}$，所以如果有解，那么求和次数最差也就是$\log 10^{12}$。而连续两次翻转是没有意义的，因此翻转最多只能夹在两次求和之间，所以最差也是$\log 10^{12}$次。所以上述循环的深度最多达到$\log 10^{12}$这个等级，而里面的差分、翻转都是$O(n)$的，因此整个算法的时间复杂度为$O(n\log 10^{12})$。事实上要比这个数小不少，因为$\log$的底数一般比$2$大很多。 这样我们就解决了这个问题。