Sereja has a sequence that consists of n positive integers, a1, a2, ..., an.
First Sereja took a piece of squared paper and wrote all distinct non-empty non-decreasing subsequences of sequence a. Then for each sequence written on the squared paper, Sereja wrote on a piece of lines paper all sequences that do not exceed it.
A sequence of positive integers x = x1, x2, ..., xr doesn't exceed a sequence of positive integers y = y1, y2, ..., yr, if the following inequation holds: x1 ≤ y1, x2 ≤ y2, ..., xr ≤ yr.
Now Sereja wonders, how many sequences are written on the lines piece of paper. Help Sereja, find the required quantity modulo1000000007 (10^9 + 7).
The first line contains integer n (1 ≤ n ≤ 10^5). The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 10^6).
In the single line print the answer to the problem modulo 1000000007 (10^9 + 7).
题目大意：
给定一个数组a：
（1）定义某个序列a小于某个序列b当且仅当a[i]≤b[i]对所有i都成立；（2）写出a的不同的所有非下降子序列；（3）若每个不同的非下降子序列的所有小于它的序列数之和定义为f，求所有f的总和。
思路：
若用s[i]表示以a[i]结尾的所有非下降子序列的f之和，那么设a[j]≤a[i]且j<i，那么s[i] = sum(s[j])*a[i] + a[i]。即在序列a[j]后接上一个a[i]可形成新的子序列。
要维护一段数字的和，树状数组就派上用场了。
这里还有一个问题，就是有可能多个a[i]相同，这样会导致重复计算。我们只需要把s[i]减去a[j]≤a[i]且j<i的sum(s[j])即可。
比如要计算序列2 2 2的时候，s[1] = {a[1]}，s[2] = {a[1,2]}，s[3] = {a[1,2,3]}。此时s[i]准确表示为：以a[i]结尾的与i之前所有子序列都不同的所有非下降子序列的f之和。
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 5 #define MOD 1000000007 6 #define MAXN 100010 7 8 struct node{ 9 int x, rank, pos; 10 } a[MAXN]; 11 12 bool cmpx(node a, node b){ 13 return a.x < b.x; 14 } 15 16 bool cmppos(node a, node b){ 17 return a.pos < b.pos; 18 } 19 20 int n, tot; 21 int b[MAXN], c[MAXN]; 22 23 inline int lowbit(int x){ 24 return x&-x; 25 } 26 27 inline int sum(int x){ 28 int ans = 0; 29 while(x > 0){ 30 ans = (ans + c[x])%MOD; 31 x -= lowbit(x); 32 } 33 return ans; 34 } 35 36 inline void add(int i, int x){ 37 while(i <= tot){ 38 c[i] = (c[i] + x)%MOD; 39 i += lowbit(i); 40 } 41 } 42 43 int main(){ 44 scanf("%d", &n); 45 for(int i = 1; i <= n; ++i) 46 scanf("%d", &a[i].x), a[i].pos = i; 47 sort(a+1, a+n+1, cmpx); 48 tot = 1; a[1].rank = 1; 49 for(int i = 2; i <= n; ++i){ 50 if(a[i].x != a[i-1].x) ++tot; 51 a[i].rank = tot; 52 } 53 sort(a+1, a+n+1, cmppos); 54 for(int i = 1; i <= n; ++i){ 55 int tmp = ((long long)sum(a[i].rank) * a[i].x % MOD + a[i].x)%MOD; 56 add(a[i].rank, (tmp - b[a[i].rank] + MOD)%MOD); 57 b[a[i].rank] = tmp; 58 } 59 printf("%d\n",sum(tot)); 60 }