Codeforces86D【莫队算法】

题意：

给一个序列和一些区间，每次询问对区间所有不同的数，求每个不同的出现的个数的平方*其值的总和

2*2*1+1*1*2

思路：

裸的莫队算法。

补：

1.cmp写错。

2.LL运算不会进行转化。

3.莫队的起始应该直接先处理好L,R。

卡了将近2.5h，水题让自己很生气。以及不会查错误真的撒比！

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

typedef pair<int,int> PII;

const int N=1e6+10;

LL num[N],res[N],c[N];

struct asd

{

    int id,left,right;

}e[200010];

int pos[200010];

int n,m;

bool cmp(asd x,asd y)

{

    if(pos[x.left]==pos[y.left])

        return x.right<y.right;

    return pos[x.left]<pos[y.left];

}

LL ans;

void solve()

{

    ans=0;

    sort(e,e+m,cmp);

    for(int i=e[0].left;i<=e[0].right;i++)

    {

    	ans=ans+(2*num[c[i]]+1)*c[i];

    	num[c[i]]++;

	}

	res[e[0].id]=ans;

	int L=e[0].left,R=e[0].right;

    for(int i=1; i<m; i++)

    {

        while(R<e[i].right)

        {

            R++;

            ans=ans+((num[c[R]]<<1)+1)*c[R];

            num[c[R]]++;

        }

        while(R>e[i].right)

        {

            num[c[R]]--;

            ans=ans-((num[c[R]]<<1)+1)*c[R];

            R--;

        }

        while(L<e[i].left)

        {

            num[c[L]]--;

            ans=ans-((num[c[L]]<<1)+1)*c[L];

            L++;

        }

        while(L>e[i].left)

        {

            L--;

            ans=ans+((num[c[L]]<<1)+1)*c[L];

            num[c[L]]++;

        }

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

    }

    for(int i=0; i<m; i++)

        printf("%I64d\n",res[i]);

}

int main()

{

    scanf("%d%d",&n,&m);

    int block=(int)sqrt(n);

    for(int i=1;i<=n;i++)

    {

        scanf("%I64d",&c[i]);

        pos[i]=(i-1)/block+1;

    }

    for(int i=0;i<m;i++)

    {

        scanf("%d%d",&e[i].left,&e[i].right);

        e[i].id=i;

    }

    solve();

    return 0;

}

巴特西

Codeforces86D【莫队算法】

最新文章

热门文章