CodeForces 315E - Sereja and Subsequences 閱讀了解+樹狀數組

     題目好久才看懂.....意思是在将這串所有非降子串值相加...子串值的定義是這串中所有元素相乘.

    ai最大為10^6...用一個10^6大的樹狀數組來維護(線段樹也可以..不過空間和時間都會差一些)...從左掃到右...插入查找更新答案...

    值得注意的是元素相等的情況..如樣例二 

             1 2 2  -> (1 , 2 , 12 , 22 , 122)=13   

    可見元素相同時不需要重複計算....是以每次在更新答案時..減去這個元素前上次更新的值... 

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<algorithm>
#define ll long long
#define oo 1000000007
#define pi acos(-1.0)
#define MAXN 10000005
using namespace std;  
ll S[MAXN],Pre[MAXN];
ll getsum(int k)
{
       ll sum=0;
       while (k)
       {
             sum=(sum+S[k])%oo;
             k-=k&(-k);
       }
       return sum;
}
void update(int k,ll x) 
{
       while (k<=MAXN)
       {
             S[k]=(S[k]+x)%oo;
             k+=k&(-k);
       }
       return;
}
int main()
{ 
       int i,n;
       ll ans;
       freopen("input.txt","r",stdin);
       freopen("output.txt","w",stdout); 
       while (~scanf("%d",&n))
       {
             memset(S,0,sizeof(S));
             memset(Pre,0,sizeof(Pre));
             ans=0;
             for (i=1;i<=n;i++)
             {
                    ll x,t;
                    scanf("%I64d",&x); 
                    t=(getsum(x)*x+x)%oo; 
                    ans=(ans+t-Pre[x])%oo;
                    update(x,t-Pre[x]);
                    Pre[x]=t;
             }
             if (ans<0) ans+=oo;
             printf("%I64d\n",ans);
       }
       return 0;
}