HDU2227(非降子序列的个数)

题目：http://acm.hdu.edu.cn/showproblem.php?pid=2227

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

分析：如果n的值比较小，那么就是一个纯粹的dp题。设dp[i]表示以a[i]为结尾非降子序列的个数，其状态转移方程为：

可以看出，这样做的时间复杂度是

，很显然不能这样做。

那么实际上，我们看到

会想到逆序数，自然也会想到求逆序数最经典的做法就是树状数组，所以问题可以转化为求逆序数的对数，那么我们可以利用dp的思想递推下去，最终求得答案，可以看出这样做的时间复杂度为

。

#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>

using namespace std;
const int N = 100005;
const int MOD = 1000000007;

struct node
{
    int id,val;
};

int n;
node a[N];
int aa[N],c[N],t[N];

bool cmp(node a,node b)
{
    return a.val < b.val;
}

int Lowbit(int x)
{
    return x & (-x);
}

void Update(int t,int val)
{
    for(int i=t; i<=n; i+=Lowbit(i))
    {
        c[i] += val;
        c[i] %= MOD;
    }
}

int getSum(int x)
{
    int ans = 0;
    for(int i=x; i>0; i-=Lowbit(i))
    {
        ans += c[i];
        ans %= MOD;
    }
    return ans;
}


int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        memset(c,0,sizeof(c));
        memset(aa,0,sizeof(aa));
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i].val);
            a[i].id = i;
        }
        sort(a+1,a+n+1,cmp);
        aa[a[1].id] = 1;
        for(int i=2;i<=n;i++)
        {
            if(a[i].val != a[i-1].val)
                aa[a[i].id] = i;
            else
                aa[a[i].id] = aa[a[i-1].id];
        }
        for(int i=1;i<=n;i++)
        {
            t[i] = getSum(aa[i]);
            Update(aa[i],t[i]+1);
        }
        printf("%d\n",getSum(n));
    }
    return 0;
}