流离之人追逐幻影。
SDOI Round2题面常年下线，不过多亏这样我可以偷懒了(这么傻还敢偷懒FuQ)
首先我们定义第i种操作是“将序列从左到右划分为$2^{n-i+1}$段，每段恰好包括$2^{i-1}$个数，然后整体交换其中两段”
根据这些操作的性质，容易发现对于一个操作序列，如果交换其中任意两个操作的顺序，这个操作序列最终产生的效果不会改变
又因为每种操作只能用一次，所以可以从小到大一个个考虑每种操作用还是不用
又容易发现，大的操作无法对小的区间产生影响，所以如果要达到有序的状态，那么在完成第i种操作后，将序列从左到右分成$2^{n-i}$个长度为$2^i$的段，每段必须要满足两个条件：
然后就可以搜索了，搜索的时候找到不合法的段，交换一下位置什么的，具体自己想想很简单的
奇怪的题，但是仔细想想也不奇怪，多自己想想啊少年别总看题解啊/(ㄒoㄒ)/~~
画了画图发现要走的路径一定在虚树上
那么动态维护一下虚树？好像没有这种算法。
其实只要按照Dfs序维护一下所有关键点的位置就好了，答案其实就是Dfs中相邻关键点的距离和再加上第一个关键点到最后一个关键点的距离。
那么用平衡树维护Dfs序，支持插入删除前驱后继，再用树上倍增求一下距离。
有点带劲的一道题
先考虑暴力的Dp，$f[i][j]$表示长度为i的序列，乘积模M为j的方案数，复杂度$O(nm^2)$。
发现可以倍增，复杂度$O(m^2\lg n)$，大概60分。
然后呢，发现M是质数，这保证了M有原根g，而1~M-1中的数都能表示成g的若干次方。
定义新的状态：$f[i][j]$表示长度为i的序列，乘积模M为$g^j$的方案数。
然后发现Dp方程是一个卷积的形式，又因为是要在模域下求方案数，所以用NTT比较合适。
经过尝试后发现，模数Mod=1004535809的原根是3，而$2^{21}|Mod-1$，非常适合用来做NTT。
最终复杂度$O(m\lg m\lg n)$
二分+最大流
当时花了两个小时教会了我零基础的儿子，他写题解写了一晚上，所以我应该不能写得更清楚了。
直接给个链接吧：Click Here
一眼SB大讨论，但是写完PushUp()以后其实就很好写了
其实就是要求一个区间中的最小生成树
那就考虑区间中的连通状态以及怎么合并咯
发现有以下五类合法的连通状态（图太丑不好意思放出来，还是点开看图吧）：
五类连通情况
每类情况中有多种可能，但是每种可能在合并时都是等价的，所以看成一类
合并时可以只连一条边，也可以两条边都连上，那么算一算发现会有$5\times 5\times 2=50$种情况要讨论
但是有些连接方式是不合法的，所以事实上只有25种情况，大力码就好了
