首先可以用线段树优化$DP$做，转移时取$0...a[i]$的最大$f$值
但我要练习$CDQ$
$LIS$是二维偏序问题，偏序关系是$i<j,\ a_i<a_j$
$CDQ$分治可以解决偏序问题
$CDQ(l,r)\ :$
$CDQ(l,mid)$
$[l,r]$按$a$排序，$[l,mid] \rightarrow\ [mid+1,r]$
$CDQ(mid+1,r)$
这个排序没法用归并排序，因为你要用最优的$f[k],k\in [mid+1,r]$来更新$k$的右面，必须先$[l,mid] \rightarrow\ [mid+1,r]$获得最优的$f[k]$才行，而那些计数类问题就不需要了
我尝试了很多写法，最后分治里还是采用了间接排序，这样不影响$i<j$这个关系
[2017-02-25]不排序用一个维护区间最大值的数据结构也可以，更新的时候取$0...a[i]$的最大$f$值(这样你还分治什么啊？！)
注意严格递增
于是$LIS$现在可以用$CDQ$水过啦！！！
其实二维的最长上升子序列用$CDQ$分治是没有意义的，无论如何都比数据结构维护多一个$log$
该死一下午就写这玩意了
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int N=5e4+,MOD=1e9+;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,a[N],ref[N];
inline bool cmp(int x,int y){return a[x]==a[y]?x>y:a[x]<a[y];}//strict
inline void mod(int &x){if(x>=MOD) x-=MOD;}
int f[N],g[N];
void CDQ(int l,int r){
if(l==r) return;
int mid=(l+r)>>;
CDQ(l,mid);
for(int i=l;i<=r;i++) ref[i]=i;
sort(ref+l,ref+r+,cmp);
int mx=,cnt=;
for(int i=l;i<=r;i++){
int id=ref[i];
if(id<=mid){
if(f[id]>mx) mx=f[id],cnt=g[id];
else if(f[id]==mx) mod(cnt+=g[id]);
}else{
if(mx+>f[id]) f[id]=mx+,g[id]=cnt;
else if(f[id]==mx+) mod(g[id]+=cnt);
}
}
CDQ(mid+,r);
}
int main(){
freopen("in","r",stdin);
n=read();
for(int i=;i<=n;i++) a[i]=read(),f[i]=g[i]=;
CDQ(,n);
int mx=,cnt=;
for(int i=;i<=n;i++){
if(f[i]>mx) mx=f[i],cnt=g[i];
else if(f[i]==mx) mod(cnt+=g[i]);
}
printf("%d",cnt%MOD);
}