Acwing–896. 最长上升子序列 II

 用vector来模拟栈，使用lower_bound来快速查找到指定区间中第一个>=指定数。
相较于普通的最长上升子序列问题，本题的数据范围从10^3提升到了10^5，所以不能用之前时间复杂度为O(n^2)的动态规划做法。

#include
using namespace std;
int a[100010];

int main()
{
int n;
cin>>n;

vectorsta;

for(int i=0;i>a[i];

sta.push_back(a[0]);

for(int i=1;ista.back())
{
sta.push_back(a[i]);
}
else
{
*lower_bo

Acwing–896. 最长上升子序列 II最先出现在Python成神之路。