hdu 2227 Find the nondecreasing subsequences (树状数组+dp+离散化）

题意：给定一个长度为n(n <= 100000)的整数序列，求其中的递增序列的个数。

对于某些序列中的递增序列的个数是可以用dp来求解的，其状态转移方程为:

dp[i] = sum(dp[j]) + 1,j < i &&a[j] < a[i]

根据状态转移方程可以得知这样dp的时间复杂度为O(n^2),而对于题目给定的10^6的数量级来说，这样dp是不行的。

那么我们根据a[j]<a[i]，可以得知，这其实就是逆序对，而求逆序对的快速方法莫过于树状数组了。

因此我们想到了树状数组，而对于题目给的a[i]元素的大小，a[i] <= 2^31，这样的数量级，很显然直接将其应用到树状数组是不可能的。

我们发现总共的元素只有n <= 10^6 个，而a[i]的最大值可以达到2^31,所以我们为了能够应用树状数组，我们想到了离散化。

离散化：我们将a[i]从小到大排个序，并将重复的元素去掉只留下一个，那么我们可以得出，每个a[i]都能对应一个数组下标，而我们就利用这个数组下标来建立树状数组。

这样在树状数组增加值的时候我们就根据dp原理，利用树状数组的性质，完成了对后面的所有元素进行求和的运算，那么最后的出来的结果就是我们要求的结果了。

下面附上代码，上面带上解释：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

#define N 100001
#define ll long long
#define Lowbit(x) ((x)&(-x))
#define M 1000000007
ll C[N];
ll num[N], t[N];
int T,tot;


void add(ll C[],ll pos,ll num) {
    while(pos <= N) {//x×î´óÊÇN
        C[pos] += num;
        if(C[pos] > M)C[pos] %= M;
        pos += Lowbit(pos);
    }
}

ll Sum(ll C[],ll end) {
    ll sum = 0;
    while(end > 0) {
        sum += C[end];
        if(sum > M)sum%= M;
        end -= Lowbit(end);
    }
    return sum;
}

int binarysearch(int x){//二分查找下标
    int mid, l = 1 ,r = tot;
    while(l <= r){
        mid = (l + r)>>1;
        if(x == t[mid])return mid;
        else if(x > t[mid]){
            l = mid + 1;
        }
        else r = mid - 1;

    }
    return -1;
}

int main() {
    int n, s,  i, j, T, k, m;
    ll ans, tmp;
    while(~scanf("%d",&T)) {
        ans = 0;
        for(i = 0; i < T; i ++) {
            scanf("%I64d",&num[i]);
            t[i+1] = num[i];
        }
        sort(t+1,t+1+T);//开始离散化
        tot = 1;
        C[tot] = 0;
        for(i = 2; i <= T; i++){//去重
            if(t[ i ] != t[i - 1]){
                t[++tot] = t[i];
                C[tot] = 0;
            }
        }
        for(i = 0; i < T; i ++){//将原来的数更改为其对应的数组下标
            num[i] = binarysearch(num[i]);
        }
        ans = 0;
        add(C,1,1);//因为每个元素都要加一个自己，所以先将所有的元素加一
        for(i = 0; i < T; i++){
            m = Sum(C,num[i]);//求出其前面有多少个小于它的数，
            ans += m; if(ans > M)ans %= M;//加起来，取模
            add(C,num[i],m);//将其值加进树状数组，原理为dp思想。
        }

        printf("%I64d\n",ans);
    }
    return 0;
}