CF86D

题解：

莫队分块

分块大小为sqrt(n)

代码：

#include<bits/stdc++.h>

using namespace std;

const int N=;

typedef long long ll;

ll a[N],cnt[N*],ans[N],res;

int n,t,L,R;

struct node{int x,y,l,p;}q[N];

int cmp(const node &x,const node &y)

{

    if (x.l==y.l)return x.y<y.y;

    return x.l<y.l;

}

void query(int x, int y, int flag)

{

    if (flag)

     {

        for (int i=x;i<L;i++)

         {

            res+=((cnt[a[i]]<<)+)*a[i];

            cnt[a[i]]++;

         }

        for (int i=L;i<x;i++)

         {

            cnt[a[i]]--;

            res-=((cnt[a[i]]<<)+)*a[i];

         }

        for (int i=y+;i<=R;i++)

         {

            cnt[a[i]]--;

            res-=((cnt[a[i]]<<)+)*a[i];

         }

        for (int i=R+;i<=y;i++)

         {

            res+=((cnt[a[i]]<<)+)*a[i];

            cnt[a[i]]++;

         }

     }

    else

     for (int i=x;i<=y;i++)

      {

        res+=((cnt[a[i]]<<)+)*a[i];

        cnt[a[i]]++;

      }

    L=x;R=y;

}

int main()

{

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

    for (int i=;i<=n;i++)scanf("%I64d", &a[i]);

    int block_size=sqrt(n);

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

     {

        scanf("%d%d",&q[i].x,&q[i].y);

        q[i].l=(q[i].x-)/block_size;

        q[i].p=i;

     }

    sort(q,q+t,cmp);

    memset(cnt,,sizeof(cnt));

    res=;

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

     {

        query(q[i].x,q[i].y,i);

        ans[q[i].p]=res;

     }

    for (int i=;i<t;i++)printf("%I64d\n",ans[i]);

    return ;

}