AtCoder Regular Contest 165-526互联

啥都不会。自闭了。

显然填充 \(1\) 不会影响 \(\text{lcm}\)。

枚举 \(n\) 的互质且 \(\text{lcm} = n\) 的因数，看和是否 \(\le n\) 即可。

注意到答案的字典序肯定大于等于原排列。

如果存在 \(\ge k\) 的上升子段就直接输出原排列，否则答案和原排列的 \(\text{lcp}\) 一定不小于 \(n - k\)。在此基础上把排序的左端点 \(l = n - k + 1\) 不断左移，如果对 \([1, n - k]\) 没有影响，就优先选左端点最小的。

二分 \(X\)。考虑对于一个长度为 \(3\) 的链，若链长 \(< X\) 就寄了。

否则把 \(< X\) 的边拎出来，若不是二分图也寄了。

显然我们想贪心地让 \([a_i, b_i], [c_i, d_i]\) 的 \(\text{lcp}\) 最小，因为这样造成的影响最小。

于是考虑连边 \(a_i \to c_i\) 表示 \(x_{a_i} \le x_{c_i}\)，若无环就有解，否则环上的点都相等，合并后更新 \(a_i, c_i\) 再做一次。如果某一时刻 \(c_i > d_i\) 了就无解。

考虑统计每个连通块被计算的概率。

设 \(f_{u, i, j}\) 为考虑 \(u\) 子树中，大小为 \(i\) 的包含 \(u\) 的连通块，除了父亲还有 \(j\) 个和这个连通块相邻的点。

转移考虑二维背包合并。

统计答案时，设连通块有 \(x\) 个点，有 \(y\) 个点与连通块相邻。那么这个连通块被统计到的概率就是 \(\frac{x! y!}{(x + y)!}\)（要保证那 \(y\) 个点在这 \(x\) 个点之前被删）。

记数字 \(i\) 的出现位置分别为 \(x_i, y_i\)。则若 \(x_i < x_j\) 且 \(y_i < y_j\)，\(i\) 移动到 \(j\) 前面更优，否则手玩一下，移动到哪边，总次数都一样。

考虑将 \((x_i, y_i)\) 抽象成二维平面的点，每次相当于选择一个左下角都没有其他点的点删掉，这样构成了一个合法的序列。但是要字典序最小，每次就选 \(i\) 最小的点删除。

主席树优化建图后，跑字典序最小拓扑序即可解决。