动态规划 FZU2236 树状数组优化

题意：
这题是求一个数列中严格递增子序列的个数。比如数列(1,3,2)的严格递增子序列有(1)、(3)、(2)、(1,3)、(1,2)，共5个。长得一样的但是位置不同的算不同的子序列，比如数列(3,3)的答案是2。
思路：
1、类LIS问题： dp[i] = sigmadp[j] + 1(j < i && a[j] < a[i])
2、离散化 + 树状数组
反思：
代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;
typedef long long ll;
int a[MAXN], b[MAXN];
ll bit[MAXN], dp[MAXN], ans;
int n;
int lowbit(int x)
{
    return x & (-x);
}
ll getSum(int i)
{
    ll res = 0;
    while(i)
    {
        res += bit[i];
        res %= MOD;
        i -= lowbit(i);
    }
    return res;
}
void update(int i, int x)
{
    while(i <= n)
    {
        bit[i] += x;
        bit[i] %= MOD;
        i += lowbit(i);
    }
}
void init()
{
    memset(bit, 0, sizeof(bit));
    memset(dp, 0, sizeof(dp));
    ans = 0;
}
int main()
{
    while(~scanf("%d", &n))
    {
        init();
        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
            b[i] = a[i];
        }
        int cnt = unique(b + 1, b + 1 + n) - (b + 1);
        for(int i = 1; i <= n; i++)
        {
            int pos = lower_bound(b + 1, b + 1 + cnt, a[i]) - b;
            dp[i] = (getSum(pos - 1) + 1) % MOD;
            ans += dp[i];
            ans %= MOD;
            update(pos, dp[i]);
        }
        printf("%lld\n", ans);
    }
}