题目：点击此处

 

莫队板子，add，和remove的时候，每增减一个数字的次数就计算一次结果，

比如加了一个数的次数，那answer+=ks*ks*s  同时减掉之前的  即answer-=（ks-1）*（ks-1）*s

 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#define ll long long
const int maxn=320010;
const int Block=555;
const int tt=1;
using namespace std;
struct node
{
    int id;
    int l,r;
}pos[1000010];

int n,q,l,r;
ll answer=0,ans[1000010],cnt[1000010],a[maxn];
bool cmp(node a,node b)
{
    if(a.l/Block!=b.l/Block)
        return a.l/Block<b.l/Block;
    return a.r<b.r;
}
void add(int positoin)
{
    cnt[a[positoin]]++;
    answer+=cnt[a[positoin]]*cnt[a[positoin]]*a[positoin];
    answer-=(cnt[a[positoin]]-1)*(cnt[a[positoin]]-1)*a[positoin];
}
void Remove(int positoin)
{
    cnt[a[positoin]]--;
    answer+=cnt[a[positoin]]*cnt[a[positoin]]*a[positoin];
    answer-=(cnt[a[positoin]]+1)*(cnt[a[positoin]]+1)*a[positoin];
}
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=0;i<n;i++)
    {
        scanf("%I64d",&a[i]);
    }
    for(int i=0;i<q;i++)
    {
        scanf("%d %d",&pos[i].l,&pos[i].r);
        pos[i].l--;pos[i].r--;
        pos[i].id=i;
    }
    sort(pos,pos+q,cmp);
    int cl=0,cr=0;
    for(int i=0;i<q;i++)
    {
        l=pos[i].l;r=pos[i].r;
        //cout<<l<<"   "<<r<<endl;
        while(cl<l) {
            Remove(cl);
            cl++;
        }
        while(cl>l) {
            add(cl-1);
            cl--;
        }
        while(cr<=r) {
            add(cr);
            cr++;
        }
        while(cr>r+1)
        {
            Remove(cr-1);
            cr--;
        }

        ans[pos[i].id]=answer;
    }
    for(int i=0;i<q;i++)
        printf("%I64d\n",ans[i]);
    return 0;
}