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
HINT
Source
题解
题目让我们求出 ∑ (a_i*a_j*a_k)，要求 i<j<k 且 a_i<a_j<a_k
我们考虑枚举中间点，这样式子就变成了∑ a_j∑a_i*a_k，也就是∑ a_j∑a_i∑a_k
但是a_i很大，所以我们还需要进行离散化
然后我们就可以用树状数组统计出小于和大于a_j的数的和
不过这里很坑，自己的程序原来一直不对
后来发现可能开long long的都要开，并且两个数乘完就要%，自己原来的程序是三个数乘完再%，就会出现负数的情况
#include<bits/stdc++.h>
#define ll long long
#define N 300005
#define mod 19260817
using namespace std;
int n,size;
ll ans;
ll tr[N],small[N],big[N],a[N],b[N];
int lowbit(int x){ return x&(-x); }
void add(int x,ll k){
while (x<=size){
tr[x]=(tr[x]+k)%mod;
x+=lowbit(x);
}
}
ll query(int x){
ll ans=;
while (x>){
ans=(ans+tr[x])%mod;
x-=lowbit(x);
}
return ans;
}
int main(){
scanf("%d",&n);
for (int i=;i<=n;i++)
scanf("%lld",&a[i]),b[i]=a[i];
sort(b+,b++n);
size=unique(b+,b++n)-b-;
for (int i=;i<=n;i++)
a[i]=lower_bound(b+,b++size,a[i])-b;
for (int i=;i<=n;i++){
add(a[i],b[a[i]]);
small[i]=query(a[i]-);
}
memset(tr,,sizeof(tr));
ll s=;
for (int i=n;i>=;i--){
s=(s+b[a[i]])%mod;
add(a[i],b[a[i]]);
big[i]=(s-query(a[i])+mod)%mod;
ans=(ans+(b[a[i]]*small[i])%mod*big[i])%mod;
}
printf("%lld\n",ans);
return ;
}