O （n*logn）求 LIS

#include<bits/stdc++.h>
using namespace std;
#define inf 2100000000
#define N 100005
int n=0,a[N],x1[N],x2[N],l1,l2;
bool read()
{
    char ch=getchar();
    if(ch==EOF) return false;
    int fl=1,x=0;
    while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) fl=-1; ch=getchar(); }
    while(ch>=‘0‘&&ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar();
    a[++n]=x;
    return true;
}
int main()
{
    while(read());
    x1[++l1]=a[1]; x2[++l2]=a[1];
    for(int i=2;i<=n;i++){
        if(a[i]<=x1[l1]) x1[++l1]=a[i];
        else{
            int pos=upper_bound(x1+1,x1+1+l1,a[i],greater<int>())-x1;
            x1[pos]=a[i];
        }
        if(a[i]>x2[l2]) x2[++l2]=a[i];
        else{
            int pos=lower_bound(x2+1,x2+1+l2,a[i])-x2;
            x2[pos]=a[i];
        }
    }
    printf("%d\n%d\n",l1,l2);
} 
//389 207 155 300 299 170 158 65