[BZOJ 5055]膜法师

2022-09-28 16:15:02

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 Input1

4
1 2 3 4

Sample Output1

Sample Input2

10
6 8 4 1 3 0 7 5 9 2

Sample Output2

1737

HINT

样例解释
对于样例 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

题解

我们枚举$j$很显然答案就是

$$\sum _{j=1} ^n (a[j]*{\sum _{i=1} ^{j-1} a[i]}*{\sum _{k=j+1} ^{n} a[k]})$$

树状数组+离散乱搞就可以了。

emmmmmm（恶膜某民命秒没）~

 //It is made by Awson on 2017.10.3

 #include <set>

 #include <map>

 #include <cmath>

 #include <ctime>

 #include <queue>

 #include <stack>

 #include <vector>

 #include <cstdio>

 #include <string>

 #include <cstring>

 #include <cstdlib>

 #include <iostream>

 #include <algorithm>

 #define LL long long

 #define Max(a, b) ((a) > (b) ? (a) : (b))

 #define Min(a, b) ((a) < (b) ? (a) : (b))

 #define sqr(x) ((x)*(x))

 #define lowbit(x) ((x)&(-(x)))

 #define count COUNT

 using namespace std;

 const int N = ;

 const LL MOD = ;

 void read(LL &x) {

     char ch; bool flag = ;

     for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || ); ch = getchar());

     for (x = ; isdigit(ch); x = (x<<)+(x<<)+ch-, ch = getchar());

     x *= -*flag;

 }

 int n;

 struct tt {

     LL val;

     int pos, rank;

 }a[N+];

 LL sum[N+], c[N+], ans;

 bool comp(const tt &a, const tt &b) {

     return a.val < b.val;

 }

 bool accomp(const tt &a, const tt &b) {

     return a.pos < b.pos;

 }

 void add(int x, LL key) {

     for (; x <= n; x += lowbit(x)) c[x] = (c[x]+key)%MOD;

 }

 LL count(int x) {

     LL cnt = ;

     for (; x; x -= lowbit(x)) cnt = (cnt+c[x])%MOD;

     return cnt;

 }

 void work() {

     scanf("%d", &n);

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

         read(a[i].val); a[i].pos = i;

     }

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

     a[].rank = ;

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

         a[i].rank = a[i-].rank+(a[i].val != a[i-].val);

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

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

         sum[i] = count(a[i].rank-);

         add(a[i].rank, a[i].val);

     }

     memset(c, , sizeof(c));

     LL cnt = ;

     for (int i = n; i >= ; i--) {

         LL tmp = count(a[i].rank);

         tmp = (cnt+MOD-tmp)%MOD;

         ans = (ans+sum[i]*tmp%MOD*a[i].val)%MOD;

         add(a[i].rank, a[i].val);

         cnt = (cnt+a[i].val)%MOD;

     }

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

 }

 int main() {

     work();

     return ;

 }

码农公寓