莫队算法的裸题。n^2可以展开成等差数列1+3+5....+2*n-1的和，这样一来插入和删除操作就变得简单多了。
#include<cstdio>
#include<cmath>
#include<algorithm>
#define MAXN 200010
using namespace std;
int a[MAXN],n,t,block,cnt[1000010];
long long ans[MAXN],now;
struct Q
{
int l,r,id;
bool operator <(const Q &b)const
{
if(l/block == b.l/block) return r < b.r;
return l < b.l;
}
}que[MAXN];
void add(int x)
{
now += (2*cnt[x]+1)*x;
cnt[x]++;
}
void del(int x)
{
now += (-2*cnt[x]+1)*x;
cnt[x]--;
}
int main()
{
scanf("%d%d",&n,&t);
for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
block = sqrt(n);
for(int i = 0; i < t; i++)
{
scanf("%d%d",&que[i].l,&que[i].r);
que[i].id = i;
}
sort(que,que+t);
int currentL = 1,currentR = 0;
for(int i = 0; i < t; i++)
{
while(que[i].l < currentL) add(a[--currentL]);
while(que[i].l > currentL) del(a[currentL++]);
while(que[i].r > currentR) add(a[++currentR]);
while(que[i].r < currentR) del(a[currentR--]);
ans[que[i].id] = now;
}
for(int i = 0; i < t; i++)
printf("%I64d\n",ans[i]);
}