MooFest 树状数组 + 前缀和

比较友好的数据结构题

建议读者好好思考思考…….

可以分析出与前缀和的关系，之后就愉快的套起树状数组辣

#include <cstdio>

#include<queue>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

const int N=200000+3;

long long C[6][N];

int  x[N],v[N],A[N], n;

int cmp(int i,int j)

{

    return x[i]<x[j];

}

int lowbit(int t)

{

    return t&(-t);

}

void update(int x,int delta,int ty)

{

    while(x<N){

        C[ty][x]+=delta;

        x+=lowbit(x);

    }

}

long long query(int x,int ty)

{

    long long tmp=0;

    while(x>0){

        tmp+=C[ty][x];

        x-=lowbit(x);

    }

    return tmp;

}

int main()

{

//  freopen("in.txt","r",stdin);

    scanf("%d",&n);

    for(int i=1;i<=n;++i)scanf("%lld%lld",&v[i],&x[i]);

    for(int i=1;i<=n;++i)A[i]=i;

    sort(A+1,A+1+n,cmp);

    long long ans=0;

    int cur;

    for(int i=1;i<=n;++i)                                          //正向枚举

    {

        cur=A[i];

        long long a=query(v[cur], 0);                //数量

        long long b=query(v[cur],1);                 //距离

    //  printf("%lld %lld\n",a,b);

        ans+=(long long)((a*x[cur]-b)*v[cur]);

        update(v[cur]+1,1,0);                             //更新比x[i]大的数量

        update(v[cur]+1,x[cur],1);                    //更新比x[i]大的距离和

    }

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

    {

        cur=A[i];

        long long a=query(v[cur],3);

        long long b=query(v[cur],4);

        ans+=(long long)(b-(a*x[cur]))*v[cur];

        update(v[cur],1,3);

        update(v[cur],x[cur],4);

    }

    printf("%lld",ans);

    return 0;

}

巴特西

MooFest 树状数组 + 前缀和

最新文章

热门文章