【XSY3312】路径(path)（trick）

原题就不说了，记录一下其中要用的一个 trick。

定理：对于一个 \(1\sim n\) 的随机排列，它的前缀最大值的期望个数为 \(O(\log n)\)。

证明：考虑元素 \(x\) 作为前缀最大值的概率，这要求 \(x+1,\cdots,n\) 都在 \(x\) 后面出现，即在排列中抽出 \(x,x+1,\cdots,n\) 这几个数，其中 \(x\) 排在第一个的概率，为 \(\frac{1}{n-x+1}\)。那么前缀最大值的期望个数为：

那么对于一类问题：

我们需要求一个问题的最优解，而这个问题可能有 \(n\) 种情况，每种情况之间相互独立，整个问题的最优解是每种情况最优解的最优解，且对于每种情况，其最优解都是可以用二分求的（能 check）。那么我们先对情况 random_shuffle，然后枚举每一种情况，记录前面枚举的所有情况的最优解，并判定这个最优解是否合法（这种情况中是否可能有比之前的最优解更优的解），若有则按原来的方法二分求，若无则跳过。那么根据上面的结论，不跳过的次数的期望是 \(O(\log n)\) 次。设 check 的时间复杂度为 \(O(C)\)，单种二分次数为 \(O(V)\)，这样时间就是 \(O(nC+C\log n\log V)\)，原来是 \(O(nC\log V)\)，可以少掉一个 \(\log V\)。

换言之，需要多组二分求最优解的时候，如果这些二分之间相互独立，可以打乱顺序，每组二分前先 check 前面得到的答案，这样期望真正需要二分的组数为 \(O(\log n)\)。