描述 Description
在你的帮助下，蔚蓝来到了埃及.在金字塔里，蔚蓝看到了一个问题，传说，能回答出这个问题的人就能受到埃及法老的祝福，可是蔚蓝日夜奋战，还是想不出来，你能帮帮他么？(XXX: 胡扯,教主怎么可能想不出来= _ =||)（WS这人说的=。=）
问题是这样的：
给定一个序列<a1,a2,...,an>.求最长上升子序列(lis)p1<p2<...<pw满足a[p1]<a[p2]<...<a[pw]
例如65 158 170 299 300 155 207 389
LIS=<65,158,170,299,300,389>。
但是，现在还有一个附加条件：求出的最长上升子序列必须含有第K项。
比如，在上面的例子中，要求求出的最长上升子序列必须含有第6项，那么最长上升子序列就是：65 155 207 389。
输入格式 Input Format
第一行是用空格隔开的两个正整数N、K，含义同上所述.
第二行N个数，即给出的序列.
输出格式 Output Format
仅有一个数，表示含有第K项的最长上升子序列的长度.
样例输入 Sample Input
5 3
1 2 3 2 1
样例输出 Sample Output
3
分析：
LIS的变形，只需两次的LIS加在一起就是答案：
第一次：从1到a[k]求出最长上升的子序列。
第二次：从a[k]到n求出最长上升子序列。
PS：由于n很大，所以要用O(n*logn)的二分算法来求LIS。
【参考二分算法】：
http://hi.baidu.com/%CA%C0%BD%E7__%CE%D2%B5%C4/blog/item/116118cf3ee3a331b600c8a1.html
【参考程序】：
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
typedef int array[300010];
array a,c,temp;
int n,k,ans;
int bsearch(int size,int ai)
{
int l=1,r=size,mid;
while (l<=r)
{
mid=(l+r)>>1;
if (c[mid-1]<ai && ai<=c[mid]) return mid;
else if (ai<c[mid]) r=mid-1;
else l=mid+1;
}
}
int Lis(array temp)
{
if (temp[0]==0) return 0;
int j,size,n=temp[0];
size=1; c[1]=temp[1];
for (int i=2;i<=n;i++)
{
if (temp[i]<=c[1]) j=1;
else if (temp[i]>c[size]) j=++size;
else j=bsearch(size,temp[i]);
c[j]=temp[i];
}
return size;
}
int main()
{
scanf("%d%d",&n,&k);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
temp[0]=0;
for (int i=1;i<=k-1;i++)
if (a[i]<a[k])
temp[++temp[0]]=a[i];
ans=0;
ans+=Lis(temp);
temp[0]=0;
for (int i=k+1;i<=n;i++)
if (a[i]>a[k])
temp[++temp[0]]=a[i];
ans+=Lis(temp);
printf("%d\n",ans+1);
return 0;
}