https://ac.nowcoder.com/acm/contest/1085/G

求区间的和，每个数乘以该数出现的次数.莫队离线处理即可。
数a，出现了n次，那么和就是nna
如果n增加1 区间和增加的值就是(n+1) * (n+1)-n * n * a
即 (2n+1） a
同理 如果n减少了1 区间和就是减去 (2 * n-1) * a
上述的n是未进行个数操作的值
如果是操作过后的，加就是 (2*n-1) * a

#include<bits/stdc++.h>
using namespace std;
int n,l=1,r=0,x;
typedef long long ll ;
ll now=0;
struct node
{
    int l,r,id;
    friend bool operator<(const node &a,const node &b)
    {
        return a.l/x==b.l/x?(a.l/x&1?a.r<b.r:a.r>b.r):a.l<b.l;
        ///分块奇偶排序
    }

} q[100005];
int read()
{
    int x;
    char c = getchar();
    while(c < '0' || c > '9')
        c = getchar();
    x = c - '0';
    while(c = getchar(), c >= '0' && c <= '9')
        x = x * 10 + c - '0';
    return x;
}

void print(int x)
{
    if(x == 0)
    {
        putchar('0');
        putchar('\n');
        return;
    }
    static char buf[50];
    int top = 0;
    while(x)
    {
        buf[++top] = x % 10 + '0';
        x /= 10;
    }
    while(top)
        putchar(buf[top--]);
    putchar('\n');
}

int a[100005],v[100005],ans[100005];
void add(int x)
{

        v[a[x]]++,now+=(2*v[a[x]]-1)*a[x];
}
void del(int x)
{

    now-=(2*v[a[x]]-1)*a[x],v[a[x]]--;

}
int main()
{

    int t;
    n=read(),t=read();
    x=sqrt(n);///块的大小
    for(int i=1; i<=n; i++)
        a[i]=read();

    for(int i=1; i<=t; i++)
    {
        q[i].l=read(),q[i].r=read();
        q[i].id=i;
    }
    sort(q+1,q+1+t);
    for(int i=1; i<=t; i++)
    {

        while(q[i].l<l)
            add(--l);
        while(q[i].l>l)
            del(l++);
        while(q[i].r<r)
            del(r--);
        while(q[i].r>r)
            add(++r);

        ans[q[i].id]=now;
    }
    for(int i=1; i<=t; i++)
        print(ans[i]);

    return 0;
}