题解：CF2152E Monotone Subsequence

· · 题解

先问一遍 1,2,\dots,n，如果结果大于等于 n+1 就直接输出，否则把结果的那些下标删了继续问。最坏情况是问了 n 次还没问出来，此时每次结果 \le n，因此必然剩下至少一个位置没被删。

考虑这样一件事：令 f_i 代表以位置 i 结尾的最长降序子序列长度，那么在这问的 n 遍中，若 i 出现在第 j 次问出来的结果中，则有 f_i=j。证明也是容易的，i 前面那 f_i 个数，每次询问会从左往右删一个，等删到自己的时候就是第 f_i 次。

观察到了这一点后，只需取出最终那个没被删的位置 pos，有 f_{pos}\ge n+1，取出以 pos 结尾的最长降序子序列即可。

submission：https://codeforces.com/contest/2152/submission/341787318