ARC165

D - Substring Comparison

simple 的好题捏！

只考虑每两个串的第一个位置，假设这两个位置不同，那么可以定出一个大小关系。将所有大小关系建成一张图，如果这张图是个 DAG，那么就可以成立了，如果有环，说明环上的点都是一样的，因此可以将这些数缩成一个点，然后把对应的串往后移一位继续做。这样只需要最多做 \(O(n)\) 次就可以判定是否为 YES，每次只需要求出 \(O(m)\) 条边的强连通分量，时间复杂度 \(O(nm)\)。

submission

E - Random Isolation

根据期望的线性性，总次数等于每个点被操作的期望之和，也即每个数被操作的概率之和。

现在我们只需要考虑一个点。考虑这个点被操作之前的连通块长什么样，需要是一个大于 \(k\) 的连通块，设大小为 \(a\)，另外边界上有 \(b\) 个点被操作过了，显然发生这样事件的概率为 \(\frac{1}{C_{a+b}^a}\)，因为另外点选没选和当前点的状态时没有关系的。然后再一步的概率是 \(\frac{1}{a}\)，因此只需要计算出每种状态的可能数即可，这可以单次 \(O(n^4)\) 树形 dp 计算，总复杂度 \(O(n^5)\)，常数极小，可以通过。

submission

F - Make Adjacent

将两个数的位置看成一个区间 \([L_i,R_i]\)，将其按照 \(L_i\) 排序，记第 \(i\) 个的右端点为 \(R_i\)，值为 \(A_i\)。

考虑怎么交换不会改变其操作次数，同时让字典序变小。考虑两个区间，如果前一个区间包含后一个区间，那么交换实际上是向最终状态靠近一步，所以是可以交换的，相反，如果不包含，那么交换实际上是背离最终状态。抽象来说，就是 \(R_i>R_j\) 可以交换，否则不行。

那么现在的问题就比较简单了，我们需要字典序最小，那么考虑第一个的时候哪些可以一路交换到最开头的地方，显然是所有的 \(R\) 的前缀最小值，从中挑出一个 \(A_i\) 最小的，然后把这个位置删了，重复即可。

如果直接使用楼房重建的线段树维护是 \(O(n\log ^2n)\) 的，不知道能不能通过。因为这题每个数只会成为最小值一次，因此在删掉一个数之后暴力找到新增的最小值加进去即可。时间复杂度 \(O(n\log n)\)。

submission