CodeForces - 86D Powerful array (莫队)

题意：查询的是区间内每个数出现次数的平方×该数值的和。

分析：虽然是道莫队裸体，但是姿势不对就会超时。答案可能爆int，所以要开long long 存答案。一开始的维护操作，我先在res里减掉了a[pos]*cnt[a[pos]]*cnt[a[pos]]，将cnt[a[pos]]+1，再将乘积加回。其实根据数学原理，K^2和（K+1)^2差值是2K+1，那么其实每次更新时只要加上或减去a[pos]*(2*cnt[pos]+1)即可，这样更高效。

#include<bits/stdc++.h>

#include<iostream>

#include<cmath>

using namespace std;

typedef long long LL;

const int maxn =2e5+;

const int maxv = 1e6+;

int block;

int a[maxn];

int cnt[maxv];

int pos[maxn];

LL ans[maxn],res;

struct Query{

    int L,R,id;

    bool operator <(const Query &p) {

        if(pos[L]==pos[p.L]) return R<p.R;

        return pos[L]<pos[p.L];

    }

}Q[maxn];

void add(int pos)

{

    res+= (LL)(cnt[a[pos]]*+)*a[pos];

    cnt[a[pos]]++;

}

void del(int pos)

{

    cnt[a[pos]]--;

    res-= (LL)(cnt[a[pos]]*+)*a[pos];

}

//#define LOCAL

int main()

{

    #ifdef LOCAL

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

        freopen("out.txt","w",stdout);

    #endif

    int N,M,K,u,v,k;

    while(scanf("%d%d",&N,&M)==){

        block = ceil(sqrt(1.0*N));

        memset(cnt,,sizeof(cnt));

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

            scanf("%d",&a[i]);

            pos[i]= i /block;

        }

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

            scanf("%d%d",&Q[i].L,&Q[i].R);

            Q[i].id = i;

        }

        sort(Q+,Q+M+);

        res=;

        int curL=,curR=;

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

            while(curL>Q[i].L)  add(--curL);

            while(curR<Q[i].R)  add(++curR);

            while(curL<Q[i].L)  del(curL++);

            while(curR>Q[i].R)  del(curR--);

            ans[Q[i].id]= res;

        }

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

            printf("%lld\n",ans[i]);

    }

    return ;

}

巴特西

CodeForces - 86D Powerful array (莫队)

最新文章

热门文章