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
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
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,k
对于枚举的j，对答案贡献a[j]∑∑a[i]a[k]
就等于a[j]*(∑a[i]*∑a[k])
维护两个线段树，每次求出和，再将a值加入
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int Mod=;
int n,sz;
ll ans,sum1[],sum2[],has[],a[],b[];
ll c[][];
void pushup(int rt,int p)
{
c[rt][p]=(c[rt*][p]+c[rt*+][p])%Mod;
}
void update(int rt,int l,int r,int x,ll d,int p)
{
if (l==r)
{
c[rt][p]+=d;
c[rt][p]%=Mod;
return;
}
int mid=(l+r)/;
if (x<=mid) update(rt*,l,mid,x,d,p);
else update(rt*+,mid+,r,x,d,p);
pushup(rt,p);
}
ll query(int rt,int l,int r,int L,int R,int p)
{
if (l>=L&&r<=R)
{
return c[rt][p];
}
int mid=(l+r)/;
ll s=;
if (L<=mid) s+=query(rt*,l,mid,L,R,p);
s%=Mod;
if (R>mid) s+=query(rt*+,mid+,r,L,R,p);
s%=Mod;
return s;
}
int main()
{
int i;
cin>>n;
for (i=; i<=n; i++)
{
scanf("%lld",&a[i]);
b[i]=a[i];
}
sort(b+,b+n+);
sz=unique(b+,b+n+)-(b+);
for (i=; i<=n; i++)
{
ll x=a[i];
a[i]=lower_bound(b+,b+sz+,a[i])-b;
has[a[i]]=x%Mod;
}
for (i=; i<=n; i++)
{
if (a[i]->=)
sum1[i]=query(,,sz,,a[i]-,)%Mod;
update(,,sz,a[i],has[a[i]],);
}
for (i=n; i>=; i--)
{
if (a[i]+<=sz)
sum2[i]=query(,,sz,a[i]+,sz,)%Mod;
update(,,sz,a[i],has[a[i]],);
}
for (i=; i<n; i++)
{
ans+=(has[a[i]]*sum1[i]%Mod)*sum2[i]%Mod;
ans%=Mod;
}
cout<<ans;
}