Find the nondecreasing subsequences
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1442 Accepted Submission(s): 516
Problem Description
How many nondecreasing subsequences can you find in the sequence S = {s1, s2, s3, ...., sn} ? For example, we assume that S = {1, 2, 3}, and you can find seven nondecreasing subsequences, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}.
Input
The input consists of multiple test cases. Each case begins with a line containing a positive integer n that is the length of the sequence S, the next line contains n integers {s1, s2, s3, ...., sn}, 1 <= n <= 100000, 0 <= si <= 2^31.
Output
For each test case, output one line containing the number of nondecreasing subsequences you can find from the sequence S, the answer should % 1000000007.
Sample Input
3
1 2 3
Sample Output
7
题目分析
题目大意：给你一个串，求这个串中不递减的子串有多少个？初一看，完全想不到会是用树状数组，但是他就是这么神奇，不递减就想到逆序数，逆序数又想到了树状数组，居然是用他。他是求子串有多少个，又要用到DP，这里DP就是用树状数组慢慢推上去，最后是注意是求和会溢出，记得%1000000007。
#include<iostream>
#include<stdio.h>
#include<memory.h>
#include<algorithm> using namespace std ; struct node
{
int val, id ;
}a[]; bool cmp(node a, node b)
{
return a.val < b.val ;
} int b[] , c[] , s[] ,n ; int lowbit( int i)
{
return i&(-i);
} void update ( int i , int x )
{
while(i<=n)
{
s[i]+=x;
if(s[i]>=)
s[i]%=;
i+=lowbit(i);
}
} int sum( int i )
{
int sum = ;
while( i > )
{
sum += s[i] ;
if( sum >= )
sum %= ;
i-=lowbit( i ) ;
}
return sum ;
} int main()
{
int i , res ;
while(scanf("%d",&n)!=EOF)
{
memset( b , , sizeof(b)) ;
memset( s , , sizeof(s)) ;
for(i=;i<=n;i++)
{
scanf("%d",&a[i].val);
a[i].id = i ;
}
sort(a+,a+n+,cmp);
b[a[].id] = ;
for(i=;i<=n;i++)
{
if(a[i].val!=a[i-].val)
b[a[i].id] = i ;
else b[a[i].id] = b[a[i-].id] ;
}
res = ;
for(i=;i<=n;i++)
{
c[i] = sum( b[i] ) ;
update ( b[i] , c[i]+ ) ;
}
printf("%d\n",sum(n));
}
return ;
}