rt

我们都知道，正常的最长不下降子序列是这样的

for(int i = 1; i <= n; i++)
{
    dp[i] = 1;
    for(int j = i - 1; j >= 1; j--)
        if(a[i] <= a[j])
            dp[i] = max(dp[i], dp[j] + 1);
    ans = max(ans, dp[i]);
}

时间复杂度是 $O(n^2)$ ，能够解决 $n \le 5000$ 的情况。

可是当我们亲爱的教练把数据提到了 $n \le 200000$ 时，这种方法就挂了。

所以求 $O(n \log n)$ 级时间复杂度的C++最长不上升子序列的代码。

最好加上注释。