hdu2227 树状数组优化dp

hdu2227 Find the nondecreasing subsequences
传送门
题意
有一个长度为(n(1leq nleq 100000))的数列，计算所有不下降子序列的个数，答案对(1e9+7)取模
题解
递推式：(dp[i]=(sum dp[j])+1,(j<i & & a[j]<=a[i]))
离散化之后遍历序列，树状数组维护(dp[i])的值，所有满足条件的(dp[j])的和就是树状数组中元素(a[i])的前缀和

#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<cstring>
#include<string>
#include<sstream>
#include<cmath>
#include<ctime>
#include<climits>
#include<algorithm>
#define LL long long
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define pi acos(-1.0)
#define eps 1e-6
#define lowbit(x) x&(-x)
using namespace std;

const int maxn=100010,mod=1000000007;
int n,a[maxn],b[maxn];
LL bit[maxn];

void add(int x,int v){
    while(x<=n){
        bit[x]=(bit[x]+v)%mod;
        x+=lowbit(x);
    }
}

int query(int x){
    int sum=0;
    while(x){
        sum=(sum+bit[x])%mod;
        x-=lowbit(x);
    }
    return sum;
}

int main(){
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            b[i-1]=a[i];
        }
        sort(b,b+n);
        int len=unique(b,b+n)-b;
        for(int i=1;i<=n;i++){
            a[i]=lower_bound(b,b+len,a[i])-b+1;
        }
        memset(bit,0,sizeof(bit));
        LL ans=0;
        for(int i=1;i<=n;i++){
            LL t=query(a[i]);
            ans=(ans+t+1)%mod;
            add(a[i],t+1);
        }
        printf("%lld
",ans);
    }
    return 0;
}