bzoj 5055: 膜法师

.

题意：题面最后三行。
题解：假如我们固定j，那么式子就变成了$a_j \times \sum a_i*\sum a_k(ij)$离散化后用个树状数组搞一搞就好了。
代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;

int n,a[300010],nn=0,mod=19260817;
long long s[300010],l[300010],r[300010],ans=0;
map<int,int>lsh;

int lb(int x)
{
    return x&-x;
}
void add(int x,long long y)
{
    for(int i=x;i<=nn;i+=lb(i))
    s[i]+=y;
}
long long get(int x)
{
    long long ans=0;
    for(int i=x;i>0;i-=lb(i))
    ans+=s[i];
    return ans;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        lsh[a[i]]=1;
    }
    for(map<int,int>::iterator it=lsh.begin();it!=lsh.end();it++)
    it->second=++nn;
    for(int i=1;i<=n;i++)
    {
        l[i]=get(lsh[a[i]]-1);
        add(lsh[a[i]],a[i]);
    }
    memset(s,0,sizeof(s));
    for(int i=n;i>0;i--)
    {
        r[i]=get(nn)-get(lsh[a[i]]);
        add(lsh[a[i]],a[i]);
    }
    for(int i=1;i<=n;i++)
    {
//      printf("%lld %lld\n",l[i],r[i]);
        ans=(ans+(l[i]%mod)*(r[i]%mod)%mod*(a[i]%mod)%mod)%mod;
    }
    printf("%lld",ans);
}