题目大意：求出一个序列中有多少个递增序列(不需要是连续的)。
题目解析：对于一个以i结尾的，那么dp[i]=sum(dp[j])+1(j<i)，相当于在最后面加一个i或者单独一个i；直接dp不可以，因为数据太大，所以这里先离散化一下，在用树状数组保存维护；
AC代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
const int maxn=100010;
const int mod=1000000007;
int n,dp[maxn],a[maxn],p[maxn];
int lowbit(int k)
{
return k&(-k);
}
void insert(int x,int v)
{
while(x<=n)
{
dp[x]=(dp[x]+v)%mod;
x+=lowbit(x);
}
}
int sum(int x)
{
int ans=0;
while(x>0)
{
ans=(ans+dp[x])%mod;
x-=lowbit(x);
}
return ans;
}
bool cmp(int c,int d)
{
if(a[c]!=a[d])return a[c]<a[d];
return c>d;
}
int main()
{
int cas,c,i;
scanf("%d",&cas);
for(c=1;c<=cas;c++)
{
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
p[i]=i;
}
sort(p+1,p+1+n,cmp);
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++)
{
insert(p[i],sum(p[i]-1)+1);
}
printf("Case %d: %d\n",c,sum(n));
}
return 0;
}