引用：
思路：
1、对于问一直接用O（n*logn）的方法求最长不升子序列即可。
求不升子序列的方法：
https://www.luogu.org/blogAdmin/article/edit/20362
2、对于问二求整个数列的最长上升子序列即可。证明如下：
（1）假设打导弹的方法是这样的：取任意一个导弹，从这个导弹开始将能打的导弹全部打完。而这些导弹全部记为为同一组，再在没打下来的导弹中任选一个重复上述步骤，直到打完所有导弹。
（2）假设我们得到了最小划分的K组导弹，从第a(1<=a<=K)组导弹中任取一个导弹，必定可以从a+1组中找到一个导弹的高度比这个导弹高（因为假如找不到，那么它就是比a+1组中任意一个导更高，在打第a组时应该会把a+1组所有导弹一起打下而不是另归为第a+1组），同样从a+1组到a+2组也是如此。那么就可以从前往后在每一组导弹中找一个更高的连起来，连成一条上升子序列，其长度即为K;
（3）设最长上升子序列长度为P，则有K<=P;又因为最长上升子序列中任意两个不在同一组内(否则不满足单调不升)，则有
P>=K，所以K=P。
#include <cstdio>
#include <algorithm>
using namespace std;
int nn[100005],n=1,l1=1,l2=1,d[100005],f[100005];
bool cmp1(int a,int b){return a>=b;}
bool cmp2(int a,int b){return a>b;}
int max(int a,int b){return a>b?a:b;}
int main(){
while(scanf("%d",&nn[n])!=EOF)n++;n--;
//求最长不升子序列
d[1]=f[1]=nn[1];
for(int i=2;i<=n;i++){
if(d[l1]>=nn[i])d[++l1]=nn[i];
else d[upper_bound(d+1,d+l1+1,nn[i],cmp2)-d]=nn[i];
if(f[l2]<nn[i])f[++l2]=nn[i];
else f[lower_bound(f+1,f+l2+1,nn[i])-f]=nn[i];
}
printf("%d\n%d",l1,l2);
return 0;
}