Find the nondecreasing subsequences
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1564 Accepted Submission(s): 563
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
Author
8600
Recommend
lcy
题目描述 ：求一段序列的上海上升序列的个数 dp[i]= sum(dp[j]+1) &&(a[j]<a[i])
因为a[j]<a[i] ，所以相当于求正序数的个数
求逆序数一般有三种解法 1 暴力 2 归并排序 3 树状数组
树状数组求法 ：
原始序列为 5 4 1 2 3
int answer=0;
一 在1的位置上加一 answer+=sum(i-1); answer=0;
0 0 1 0 0
二在2的位置上加一 answer+=sum(3); answer=1;
0 0 1 1 0
三在3的位置上加一 answer+=sum(4); answer=3
0 0 1 1 1
四 在四的位置上加一 answer+=sum(1);answer=3;
0 1 1 1 1
五 在五的位置上加一 answer+=sum(0);answr=3;
1 1 1 1 1
此题要求所有的上升序列的个数，有了递推式应该很好求，
可是我陷入了一个误区 ，认为既然是递推式，那么就应该按照天然的顺序，逐个递推（因为计算当前状态值需要用到前面所有的状态值），
可是要求正序数的话需要从小到大，逐个放入，计算前面的数之和，瞬间就无语了，怎么办呢？观察递推式 dp[i]= sum(dp[j]+1) &&(a[j]<a[i])
如果从小到大放的话，假设放i位置，那么i之前的就是比它小的已经放过的，没有放的就是对i状态的值无影响的，先放还是后放对i
状态没有影响，这样我们就可以去掉对i来说的冗余信息，相当于只对 a[j] < a[i] 的 j 进行递推，
我们设 A[i]代表以i结尾的上升序列的个数，A[i]=sum(i-1)+1;sum(i-1)代表之前所有的上升序列的个数，sum(i-1) == A[1]+A[2]+A[3]+.....+A[i-1];
假设从小到大进行求解，利用暴力求和，时间复杂度太高，
那么我们利用树状数组进行点（A[i]）修改和查询操作，时间复杂度降为 long(N);
也可利用线段树进行点修改和查询操作
采用树状数组，从小到大 ，放入 它自己的位置，然后更新A[i]，那么答案就是sum(N);
假设原始序列为 5 4 1 2 3
一
0 0 0 0 0
二
0 0 1 0 0
三
0 0 1 2 0
四
0 0 1 2 4
五
0 1 1 2 4
六
1 1 1 2 4
那么答案就是1 + 1 + 1 + 2 + 4=9，利用树状数组进行求和
#include <iostream> #include <cstdio> #include <time.h> #include <stdlib.h> #include <cstring> #include<algorithm> #define M 100100 #define MOD 1000000007 #define LL long long using namespace std; struct node { LL value,id; }; bool cmp (node a,node b) { if(a.value!=b.value) return a.value<b.value; else return a.id<b.id; } node a[M]; LL dp[M]; LL c[M]; LL N; void init() { memset(a,0,sizeof(a)); memset(dp,0,sizeof(dp)); memset(c,0,sizeof(c)); } //树状数组 LL lowbit(LL x) { return x&(-x); } LL sum(LL x) { LL ret=0; while(x>0) { ret=ret%MOD; ret+=c[x]; x-=lowbit(x); } return ret%MOD; } void add(LL x,LL extra) { while(x <= N) { c[x]=c[x]%MOD; c[x]=c[x]+1+extra; //A[i]加上i之前的所有的上升序列的个数 A[i]=sum(i-1)+1;sum(i-1)代表之前所有的上升序列的个数 x+=lowbit(x); } } LL solve() { add(a[1].id,0); // answer+=sum(a[1].id); //printf("%lld ",sum(a[1].id)); for(int i=2;i<=N;i++) { add(a[i].id,sum(a[i].id-1)); //A[i]加上i之前的所有的上升序列的个数 A[i]=sum(i-1)+1;sum(i-1)代表之前所有的上升序列的个数 // answer=answer % MOD; // answer+=sum(a[i].id); // printf("%lld ",sum(a[i].id)); } return sum(N) % MOD; } int main() { while(~scanf("%d",&N)) { init(); for(int i=1;i<=N;i++) { scanf("%I64d",&a[i].value); a[i].id=i; //printf("%I64d %I64d ",a[i].value,a[i].id); } /*for(int i=1;i<=N;i++) { printf("%lld %lld ",a[i].value,a[i].id); }*/ sort(a+1,a+N+1,cmp); printf("%I64d ",solve()); } return 0; }