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

HINT

Source

By szwujq

 

题解

题目让我们求出 ∑ (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的都要开,并且两个数乘完就要%,自己原来的程序是三个数乘完再%,就会出现负数的情况

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 #define N 300005
 4 #define mod 19260817
 5 using namespace std;
 6 int n,size;
 7 ll ans;
 8 ll tr[N],small[N],big[N],a[N],b[N];
 9 int lowbit(int x){ return x&(-x); }
10 void add(int x,ll k){
11     while (x<=size){
12         tr[x]=(tr[x]+k)%mod;
13         x+=lowbit(x);
14     }
15 }
16 ll query(int x){
17     ll ans=0;
18     while (x>0){
19         ans=(ans+tr[x])%mod;
20         x-=lowbit(x);
21     }
22     return ans; 
23 }
24 int main(){
25     scanf("%d",&n);
26     for (int i=1;i<=n;i++)
27         scanf("%lld",&a[i]),b[i]=a[i];
28     sort(b+1,b+1+n);
29     size=unique(b+1,b+1+n)-b-1;
30     for (int i=1;i<=n;i++)
31         a[i]=lower_bound(b+1,b+1+size,a[i])-b;
32     for (int i=1;i<=n;i++){
33         add(a[i],b[a[i]]);
34         small[i]=query(a[i]-1);
35     }
36     memset(tr,0,sizeof(tr));
37     ll s=0;
38     for (int i=n;i>=1;i--){
39         s=(s+b[a[i]])%mod;
40         add(a[i],b[a[i]]);
41         big[i]=(s-query(a[i])+mod)%mod;
42         ans=(ans+(b[a[i]]*small[i])%mod*big[i])%mod;
43     }
44     printf("%lld\n",ans);
45     return 0;
46 }
View Code

 

爱编程-编程爱好者经验分享平台

文章评论

  

版权所有 爱编程 © Copyright 2012. w2bc.com. All Rights Reserved.
闽ICP备12017094号-3