首页 > 代码库 > 树状数组
树状数组
求有序数列的排列数
如{1,2,3,4,5}的排序数目
{1},{2},{3},{4},{5},{1,2},{1,3},{1,4}......
代码:
#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <algorithm>
using namespace std;
struct node
{
int val, id;
}a[100005];
bool cmp(node a, node b)
{
return a.val < b.val;
}
int b[100005], c[100005], s[100005], n;
int lowbit(int i)
{
return i&(-i);
}
void update(int i, int x)
{
while(i <= n)
{
s[i] += x;
if(s[i] >= 1000000007)
s[i] %= 1000000007;
i += lowbit(i);
}
}
int sum(int i)
{
int sum = 0;
while(i > 0)
{
sum += s[i];
if(sum >= 1000000007)
sum %= 1000000007;
i -= lowbit(i);
}
return sum;
}
int main()
{
int i, res;
while(scanf("%d", &n) != EOF)
{
memset(b, 0, sizeof(b));
memset(s, 0, sizeof(s));
for(i = 1; i <= n; i++)
{
scanf("%d", &a[i].val);
a[i].id = i;
}
sort(a+1, a+n+1, cmp);
b[a[1].id] = 1;
for(i = 2; i <= n; i++)
{
if(a[i].val != a[i-1].val)
b[a[i].id] = i;
else b[a[i].id] = b[a[i-1].id];
}
res = 0;
for(i = 1; i <= n; i++)
{
c[i] = sum(b[i]);
update(b[i], c[i]+1);
}
printf("%d\n", sum(n));
}
return 0;
}