树状数组+找规律
Codeforces JAVA8 比 JAVA6 慢了快一倍.......
C. Sereja and Subsequences time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output
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 (109?+?7).
Input
The first line contains integer n (1?≤?n?≤?105). The second line contains n integers a1,?a2,?...,?an (1?≤?ai?≤?106).
Output
In the single line print the answer to the problem modulo 1000000007 (109?+?7).
Sample test(s) input
1
42
output
42
input
3
1 2 2
output
13
input
5
1 2 3 4 5
output
719
/**
* Created by ckboss on 14-9-8.
*/
import java.util.*;
public class SerejaandSubsequences {
static final long mod = 1000000007;
static int n;
static long[] a = new long[100100];
static long[] tree = new long[1000100];
static long[] dp = new long[100100];
static int lowbit(int x){
return x&(-x);
}
static void ADD(int pos,long value){
for(int i=pos;i<=1000010;i+=lowbit(i)){
tree[i]+=value;
if(tree[i]>=mod) tree[i]-=mod;
}
}
static long SUM(int pos){
long ret=0;
for(int i=pos;i>0;i-=lowbit(i)){
ret+=tree[i];
if(ret>=mod) ret-=mod;
}
return ret;
}
public static void main(String[] args){
Scanner in = new Scanner(System.in);
n=in.nextInt();
for(int i=1;i<=n;i++){
a[i]=in.nextInt();
long sum=SUM((int)a[i]);
long jian=SUM((int)a[i])-SUM((int)(a[i]-1));
long temp=((sum*a[i])%mod+a[i]-jian+mod)%mod;
dp[i]=(dp[i]+temp)%mod;
ADD((int)a[i],temp);
}
long ans=0;
for(int i=1;i<=n;i++){
ans=(ans+dp[i])%mod;
}
System.out.println(ans);
}
}