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

1 2 3

Sample Output

题目分析

题目大意：给你一个串，求这个串中不递减的子串有多少个？初一看，完全想不到会是用树状数组，但是他就是这么神奇，不递减就想到逆序数，逆序数又想到了树状数组，居然是用他。他是求子串有多少个，又要用到DP，这里DP就是用树状数组慢慢推上去，最后是注意是求和会溢出，记得%1000000007。

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<memory.h>
 4 #include<algorithm>
 5 
 6 using namespace std ;
 7 
 8 struct node 
 9 {
10     int val, id ;
11 }a[100005];
12 
13 bool cmp(node a, node b)
14 {
15     return a.val < b.val ;
16 }
17 
18 int b[100005] , c[100005] , s[100005] ,n ;
19 
20 int lowbit( int  i)
21 {
22     return i&(-i);
23 }
24 
25 void update ( int i , int x )
26 {
27     while(i<=n)
28     {
29         s[i]+=x;
30         if(s[i]>=1000000007)
31             s[i]%=1000000007;
32         i+=lowbit(i);
33     }
34 }
35 
36 int sum( int i )
37 {
38     int sum = 0 ;
39     while( i > 0 )
40     {
41         sum += s[i] ;
42         if( sum >= 1000000007)
43             sum %= 1000000007;
44         i-=lowbit( i ) ;
45     }
46     return sum ;
47 }
48 
49 
50 
51 int main()
52 {
53     int i , res ;
54     while(scanf("%d",&n)!=EOF)
55     {
56         memset( b , 0 , sizeof(b)) ;
57         memset( s , 0 , sizeof(s)) ;
58         for(i=1;i<=n;i++)
59         {
60             scanf("%d",&a[i].val);
61             a[i].id = i ;
62         }
63         sort(a+1,a+n+1,cmp);
64         b[a[1].id] = 1 ;
65         for(i=2;i<=n;i++)
66         {
67             if(a[i].val!=a[i-1].val)
68                 b[a[i].id] = i ;
69             else b[a[i].id] = b[a[i-1].id] ;
70         }
71         res = 0 ;
72         for(i=1;i<=n;i++)
73         {
74             c[i] = sum( b[i] ) ;
75             update ( b[i] , c[i]+1 ) ;
76         }
77         printf("%d
",sum(n));
78     }
79     return 0 ;
80 }

View Code