【bzoj5055】膜法师（离散化+树状数组）

　　传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=5055

　　这道题……不得不说，从标题到题面都能看出一股浓浓的膜法气息……苟……

　　题意就是统计顺序三元组（似乎可以这么叫吧）的乘积和。顺序三元组有个低阶版本叫做顺序对，顺序对有一个亲兄弟叫做逆序对。既然我们可以用值域树状数组来处理关于顺/逆序对，因此也可以尝试用同样的方法处理这道题。

　　我们可以固定a[j]，求剩下的a[i]和a[k]。ans=a[j]*sigma(a[i]*a[k])

　　于是我们就把一个顺序三元组拆成了两个顺序对，一个是a[i]<a[j]且i<j，另一个是a[j]<a[k]且j<k，且这两个逆序对是不干扰的，可以直接把结果乘起来。

　　所以我们对于每个数，求出左边比它小的数的总和，和右边比他大的数的总和，记为l[i]和r[i]。于是ans=sigma(a[i]*l[i]*r[i])

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<ctime>

#include<algorithm>

#include<queue>

#include<vector>

#define ll long long

#define mod 19260817

using namespace std;

inline ll read()

{

    ll tmp=; char f=,c=getchar();

    while(c<''||''<c){if(c=='-')f=-; c=getchar();}

    while(''<=c&&c<=''){tmp=tmp*+c-''; c=getchar();}

    return tmp*f;

}

ll c[];

ll a[],id[],rk[];

ll l[],r[];

int n;

bool cmp(ll x,ll y){return a[x]<a[y];}

void add(int x,ll k){while(x<=n){c[x]+=k; x+=x&(-x);}}

ll getsum(int x){ll sum=; while(x){sum+=c[x]; x-=x&(-x);} return sum;}

int main()

{

    int i;

    n=read();

    for(i=;i<=n;i++)a[i]=read(),id[i]=i;

    sort(id+,id+n+,cmp);

    rk[id[]]=;

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

        rk[id[i]]=rk[id[i-]];

        if(a[id[i]]>a[id[i-]])++rk[id[i]];

    }

    for(i=;i<=n;i++)c[i]=;

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

        l[i]=getsum(rk[i]-)%mod; add(rk[i],a[i]);

    }

    for(i=;i<=n;i++)c[i]=; ll sum=;

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

        r[i]=(sum-getsum(rk[i]))%mod; add(rk[i],a[i]); sum+=a[i];

    }

    ll ans=;

    for(i=;i<=n;i++)ans=(ans+l[i]*r[i]%mod*a[i])%mod;

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

    return ;

}

bzoj5055

巴特西

【bzoj5055】膜法师（离散化+树状数组）

最新文章

热门文章