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

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

———————————————————————————

这道题我们可以先考虑二元组的答案

那么单独考虑一个i 以i为结尾的二组的答案的和就是v[i]*比v[i]小的x的v[x]和

那么在知道了二元组答案的情况下我们很容易就可以求出答案辣

其实就是把二元组得到的答案作为权值扔进树状数组就可以了

#include<cstdio>

#include<cstring>

#include<algorithm>

const int M=1e6+,mod=;

char buf[*M],*ptr=buf-;

int read(){

    int ans=,f=,c=*++ptr;

    while(c<''||c>''){if(c=='-') f=-; c=*++ptr;}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=*++ptr;}

    return ans*f;

}

int n,k,ly,ans;

int s1[M],s2[M],v[M],x[M];

#define lowbit(x) x&-x

void ins(int x,int v,int w[]){while(x<=n) w[x]=(w[x]+v)%mod,x+=lowbit(x);}

int query(int x,int w[]){int sum=; while(x) sum=(sum+w[x])%mod,x-=lowbit(x); return sum;}

int main(){

    fread(buf,,sizeof(buf),stdin);

    n=read();

    for(int i=;i<=n;i++) v[i]=read(),x[i]=v[i];

    std::sort(x+,x++n);

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

        k=std::lower_bound(x+,x++n,v[i])-x;

        ly=query(k-,s1); ins(k,v[i],s1);

        ans=(ans+1LL*v[i]*query(k-,s2)%mod)%mod;

        ins(k,1LL*ly*v[i]%mod,s2);

    }printf("%d\n",ans);

    return ;

}

秒客网