bzoj 5055: 膜法师 -- 树状数组

5055: 膜法师

Time Limit: 10 Sec  Memory Limit: 128 MB

Description

在经历过1e9次大型战争后的宇宙中现在还剩下n个完美维度，

现在来自多元宇宙的膜法师，想偷取其中的三个维度为伟大的长者续秒，

显然，他能为长者所续的时间，为这三个维度上能量的乘积，

但目前的宇宙很不乐观，胡乱偷取可能造成维度的崩溃，

所以，他必须按逆序偷取这些维度，且在偷取中，

每次偷取的维度的能量必须严格小于他上次偷取的能量，

由于膜法师生活在多元宇宙，所以他可以让所有可能的偷取方案全部发生

题目描述

但他数学不好，所以找到了你帮他求出能为长者续几秒，

你要做的，就是在给定的维度序列a中，

求出所有满足i<j<k且ai<aj<ak的ai*aj*ak的和

即 ∑ (a_i*a_j*a_k)，要求  i<j<k  且 a_i<a_j<a_k

 

Input

第一行1个数 n

第二行n个数 a_i

 

Output

一个数，表示能为长者续几秒，由于长者是不朽的，

所以能活很久，不妨将答案对**19260817**取模吧

 

Sample Input

样例1
4
1 2 3 4

样例二
10
6 8 4 1 3 0 7 5 9 2

Sample Output

样例输出1
50

样例输出2
1737

样例解释
对于样例 1
有满足条件的序列为
{1，2，3}——6
{1，2，4}——8
{1，3，4}——12
{2，3，4}——24
ans=6+8+12+24=50

数据范围
　　30%的数据n<=300
　　60%的数据n<=3000
　　100%的数据n<=300000
　　0<=a[i]<=2147483647

HINT

数组先离散化一下，然后搞两下树状数组就好啦

注意 数字是严格小于的，询问的时候需要 -1，离散化的时候判断一下相等的情况

#include<map>

#include<cmath>

#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define mod 19260817

#define ll long long

#define N 300010

inline ll rd()

{

    ll x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

int n;

struct qaz{int d,p;ll x;}a[N];

bool cmp(qaz a,qaz b){return a.x<b.x;}

bool cmp2(qaz a,qaz b){return a.d<b.d;}

ll f[N][],c[N][],ans;

void add(int x,ll v,int p){for(int i=x;i<=n;i+=i&(-i)) c[i][p]=(c[i][p]+v)%mod;}

ll fd(int x,int p){ll sum=;for(int i=x;i;i-=i&(-i)) sum=(sum+c[i][p])%mod;return sum;}

int main()

{

    n=rd();

    for(int i=;i<=n;i++) a[i].x=rd(),a[i].d=i;

    sort(a+,a+n+,cmp);a[].x=-;

    for(int i=;i<=n;i++) a[i].p=(a[i].x==a[i-].x?a[i-].p:i);

    sort(a+,a+n+,cmp2);

    for(int i=;i<=n;i++)

    {

        f[i][]=(a[i].x*fd(a[i].p-,))%mod;

        add(a[i].p,a[i].x,);

    }

    for(int i=;i<=n;i++)

    {

        f[i][]=(a[i].x*fd(a[i].p-,))%mod;

        add(a[i].p,f[i][],);

    }

    for(int i=;i<=n;i++) ans=(ans+f[i][])%mod;

    printf("%lld\n",ans);

    return ;

}