小蒟蒻获得的赞最多的一篇题解
第一问很容易就可以想到是求一个最长不上升子序列
但是第二问就需要一个转换的思想了
我们可以把问题中需要几组导弹转化成求一个最长上升子序列
证明：
首先我们把这些导弹分为$s$组($s$即为所求答案)
可以看出每一组都是一个不升子序列
划分完后我们在组一里找一个原序列里以组一的开头点连续的不升子串的最后一个元素，可以知道在组2中一定有一个大与它的点
(如果组二中没有的话，那么组二中最高的导弹高度必然小于这个点，而其他的高度都小于这个高度而且是递减或相等的，那么没有必要再开一个组二了，矛盾，所以不存在找不到比他大的点的情况)
以此类推，对于每一个$k$组$(1<=k<n)$都可以找到这样的一些点
所以把这些点连起来，就是一条上升子序列。
设最长上升子序列长度为$l$
所求上升子序列为$h$
那么$h<=l$
因为最长上升子序列任意两个不在一组内
(如果在同一个组内，则每个组的数不成为一个不生子序列，矛盾）
所以$l==h$
比较难理解
我们来看组数据
$389 207 155 300 299 170 158 65$
组一 $389 207 155 65$
组二 $300 299 170 158$
步骤一中我们一开始找到的点是$1$
因为如果找$65$不好解释，所以我们找原数列里连续的最后一个即$155$
组二里可以找到$300$比他大
所以最长上升子序列长度为$2==$答案
到这里我们发现只要求最长不升子序列和最长上升子序列就好了
下面说最长上升子序列的$O(nlogn)$求法（最长不升子序列同理）
数组$a$为要求的数列
首先我们开一个数组$k$
$k[lis]$记录$lis$长的上升子序列的最后一个数
$len$表示最长的长度
初始化$len=0，k[0]=-$无限
我们可以很轻松的看出k是一个有序的（递增）
如果$ai>k[len]$
$k[len=1]=i$
不然每次在k里面二分查找第一个大于等于它的数，下标为$x$
比较大小，$k[x]=min(k[x],a[i])$
因为我们要求最长的，所以我们要尽可能的让最后一位小（贪心思想）
最后输出$len$即可
证明
$k$数组一定是一个有序的上升序列
因为它记录的是长为$x$的上升序列的最后一位
如果不是上升的，那么它必然可以加入以$k[x+1]$结尾的上升序列，矛盾
#include <iostream>
#include <algorithm>
using namespace std;
int i,g[10000000],a[10000000],len,k[10000000],zen;
const int inf=0x7f7f7f7f;
int main()
{
g[0]=-inf;
k[0]=inf;
while(cin>>a[++i])
{
if(a[i]<=k[zen]){zen++;k[zen]=a[i];}
else
{
int h=0,d=zen,mid;
while(h<d)
{
mid=(h+d)>>1;
if(k[mid]>=a[i])
h=mid+1;
else
d=mid;
}//二分在k数组里找第一个小于a[i]的数
k[h]=max(k[h],a[i]);//进行比较，贪心思想
}
if(a[i]>g[len])
{
len++;
g[len]=a[i];
continue;
}
int x=0,y=len,mid;
while(x<y)
{
mid=(x+y)>>1;
if(g[mid]>=a[i])
y=mid;
else
x=mid+1;
}//二分在g数组里找第一个大于等于a[i]的数
g[x]=min(g[x],a[i]);//进行比较，贪心思想
}
cout<<zen<<endl<<len;
return 0;
} 文章中关于对求最长上升子序列的证明，部分参考了这位大佬的题解，致以最诚挚的感谢jjpjj的证明方法
谨以此题纪念我的luogu绿名
