123
初赛
多折较差验证
有区间 dp 易得 \(f_{i,j}\) 表示当前收缩到 \([i,j]\) 区间时的最小操作次数和代价，转移显然，时间复杂度 \(O(n^3)\)。
考虑两个串 a,b 且 a 是 b 的一个前缀，由于可以复制 b 的操作，所以 a 的总代价肯定是不超过 b 的，这里有一个单调性，这启发我们每次折最长的一段，且折最长的一段的不对称程度也是最小的，所以结果不劣。
那么可以对每个点开个 set 存储这个点作为区间端点时哪些区间是可行的，在转移的时候只需在 set 上二分即可找到转移点，总复杂度 \(O(n^2\log n)\)。
分治乘法
有显然分治做法：把每个1都生成出来，后根据位置分治合并。这样操作的总次数为 \(n+\frac{n}{2}+\frac{n}{4}+\cdots=2n \leq 10^6\)，总代价为 \(n\log n \approx 10^7\)，总代价不可接受，但是总操作次数可以接受。
但是总代价只是上限的两倍，我们只需要做比较小的优化就可以通过此题。一种优化方案是在分治过程中先处理左右两边相同部分，把左边造出来后通过 3 操作平移到右边，后再进行合并，实测可以通过此题。
套娃
首先有一个结论，记极短的 mex 区间为不能在不改变 mex 值的情况下继续缩短区间，则极短的 mex 区间个数是 \(\Theta(n)\) 的，证明如下：
设 \([l,r]\) 为一个极短 mex 区间，则显然 \(a_l\neq a_r\)，且 \(a_l,a_r\) 在 \([l,r]\) 中唯一，不妨设 \(a_l>a_r\)。
若存在 \(r'>r,a_l>a_{r'}\) 且 \([l,r']\) 仍为极短 mex 区间，有不等式 \(mex(l,r)>a_l>a_{r'}\) 则 \(a_{r'}\) 必然在 \([l,r]\) 中出现，故 \([l,r']\) 不为极短 mex 区间。
这说明对于 \(a_l>a_r\) 的情况最多只有 1 个极短 mex 区间，对于 \(a_l<a_r\) 情况同理，故总数为 \(\Theta(n)\)。
同时极短 mex 区间还有一个性质：\(mex_x\) 区间一定可以由某个 \(mex_t\) 区间向两边扩展到第一个 \(t\) 而得到。证明如下：
考虑一个极端 mex 区间 \([l,r]\)，则 \(a_l\) 在 \((l,r)\) 中没有出现，考虑删去 \(a_l\) 后，mex 变为 \(a_l\)，不妨设 \(mex_{a_l}\) 的极短区间为 \([L,R]\)，则 \(a_r\) 必然在其中出现，又由于 \(a_r\) 在 \([l,r]\) 唯一，故 \(R=r\)。
根据这个性质，就可以求出所有极短 mex 区间。从小往大枚举，在去除非极短区间后进行扩展，并用主席树维护 \(lst_u\) 表示 \(u\) 最后一次出现的位置来 \(O(\log n)\) 求出区间 mex 即可，总复杂度为 \(O(n^2\log n)\)。
考虑本题，对于一个极短 mex 区间 \([l,r]\)，设 \(L,R\) 为两端第一次出现 mex 的位置，则 \(\forall len\in[r-l+1,R-L+1]\) 的长度该极短 mex 区间都能被包含，故该 mex 相当于区间加入了一段长度，于是可以进行差分，用 set 和 cnt 维护当前未出现的数，即可回答询问。
Code: https://loj.ac/s/2097334s
排序大师
抄的洛谷题解，不是很懂怎么严格证明正确性。
称相邻的 i 和 i+1 为一个链接，实际上我们需要最大化链接数量，那么考虑每次将最小的未归位的 i 归位，由于归位操作我们自然可以得到一个链接的增加，后考虑一个最小的 j 使得 \(pos_j < pos_i\)，额外将 j-1 和 j 链接起来，这样每次操作都能至少得到 2 个链接，这样做就能通过本题。