Nonsense Time[hdu6635]

发表于 分类于

题意

一个随机的排列 $p$，一开始所有位置都不能用。每次随机加一个位置使其变得可用，然后求当前最长上升子序列的长度。

$n\leq 50000,T\leq 3$

时限 $14s$

题解

一个很重要的前置知识：长度为 $n$ 的排列的最长上升子序列的长度的期望是 $O(\sqrt n)$

记住就好，不会证明…

因此每个位置有 $O(\frac{1}{\sqrt n})$ 的概率在LIS上。

本题倒着做或许会方便一些，每次删掉一个数。

那么每次先暴力求出LIS及其位置。如果每次使其不可用的位置不在LIS上，那么不管它。否则暴力再算一遍LIS。

期望复杂度 $O(\frac{n^2\log n}{\sqrt n})=O(n\sqrt n\log n)$

这是一道用了比较重要的性质的题，在此记录一下以免忘记。

程序

咕咕咕