Find the nondecreasing subsequences
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1182 Accepted Submission(s): 408

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

题意：
给你一个有序序列, 求有多少个不下降子序列

结果对 10^9+7 取模

注意：不下降【相等也可以】
每个元素本身也算一个

算法：离散化+树桩数组+简单dp 思想

思路：
这道题目的数据比较大 1 <= n <= 100000 0 <= si <= 2^31 如果数据比较小直接 DP就可以解决了。当然这些比赛的时候都没有想到, 找题解的时候突然看到了奋斗青春 的 DP 思想，然后去神牛 Maxtri67 那儿学了下什么是离散化 , 后来kuangbin 大神又给我说了另外一种离散化的思想的两种实现方法。
012

我们先分析一下假设数据比较小的情况：

dp[a[j]]=sum( dp[a[i]] )+1; (i>=1 && i=a[i]) //单独的a[j]也算一个

//a[] 存序列中的元素值, dp[i] 表示值为 i 结尾形成的子序列的个数
int ans = 0; // 暂且不考虑对 10^9+7 取模的情况
for(int i = 1; i <= n; i++)
{
    for(int j = 1; j < i; j++) //如果 a[i] 出现在 a[j] 后面而又不比 a[j] 小, 那么可以直接加在 a[j] 后面,形成新的子序列
    {
        if(a[i] >= a[j])
        dp[a[i]] += dp[a[j]];
    }
    dp[a[i]]++; //自己单独也是一个
    ans += dp[a[i]]; 
}
printf("%d\n", ans);

但是 a[i] 的值最大到了 2^31 , 明显不可能开一个这么大的数组
如是需要离散化一下, 把结果映射到 1-n 这个区间,等下我会详细的解释下我对这题的离散化的理解, 第一个离散化题目Orz
说的这么高深, 其实一般的离散化简单排序下再做些小处理就可以了。

现在我们先抛下离散化, 看下这个 DP 的结构, 就是对前面满足条件的求和有木有, 考虑到 n 比较大, 更新的次数比较多, 那么我们是否可以想到一个快速求和的方法, 树状数组正好能快速求一段序列的和的, 那么我们是否可以把这道题目往树桩数组上想。

至于关于树状数组的理解, 我是看的 lrj 《训练指南》P194-P196 上的介绍了,网上也有很多资料,自认为还没有办法说的特别清楚,这里不再仔细介绍, 你只需要记住树桩数组能够快速的求一段序列的和,并且能够快速更新每一个点的值那么就可以往下看了。
推荐树状数组入门题目：hdu 1166 敌兵布阵 我的代码：点击打开链接

如果实在不了解的：先记住下面这句话, 然后再继续往下看。看过树状数组的可以直接忽略。。。

树桩数组的下标从 1 开始到 N , 数组 a[] 记录序列的值 c[i] 记录以 a[i] 结束的某段 a[j]到 a[i] 的连续和
ＰＳ：具体是那一段，这里我一句两句也说不清楚，先记住好了，对下面的思想的分析没有太大的影响

　　　　　　　　　　　　有两个函数：　add(int i , int val) // 把a[i] 更新加上 val ,同时更新相应的一段 c[]
sum(int i) // 求 a[1] +a[2] +...+ a[i] 的连续和


如何转换成树桩数组求解？

什么是离散化？关于这题如何离散化？

开始准备分开写，但是感觉说不清楚，就先放一起了。有兴趣的童鞋可以先去看下 Maxtri67 离散化的笔记 离散化

这题求的是不下降子序列的个数。
也就是说符合要求的序列元素的后面的一个的值总是大于或等于前一个元素的【废话一句可以忽略Orz】
那么我们可以先对输入的元素 a[i] 按照从小到大做一个排序处理。

这样排序后前面的数字肯定小于等于后面的数字是不是。那么依次遍历的时候,直接把当前的数字插入到前面已经处理过的数字所形成所
有子序列后面那么就可以形成新的子序列了。那么排序后,我们只要弄个数组把每一个以 a[i] 结尾的对应的序列个数记录
下来就可以了, 【顺序打乱了,后面会说怎么处理,这里先不管】假设记录个数的数组是 num[] 那么最后就把每一个 num[] 相加是不是就是最后
的结果了。中间注意下取模。

好像有点树状数组的感觉了，不过还是没什么用的样子，继续往下看。。。
但是这样嵌入了离散化的思想：把原来的应该开到 2^31 的数组 dp [] 优化到了长度为 100000 num[] 直接映射到 1 到 N 求解
又装逼了, 不就是个排序处理还说的这么高深。


下面以类似于样例中的已经排序好了的解释下上一段关于离散化的思想：

3
100 200 300

对于第一个数 100 ：以 1 结尾形成一个不下降子序列就是他自己 num[1] = 1