rt，在 vjudge 上测的，TLE on #6

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,M=1e6+5;
struct node{
	int l,r,id;
}ask[N];
int n,q,a[N],block;
int pos[N],l,r;
long long sum,ans[N],cnt[M];

template<typename T>
inline void read(T &x){
    char c;
    x=0;
    int fu=1;
    c=getchar();
    while(c>'9'||c<'0'){
        if(c=='-')fu=-1;
        c=getchar();
    }
    while(c<='9'&&c>='0'){
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    x*=fu;
}
template<typename T>
inline void print(T x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)print(x/10);
    putchar(x%10+'0');
}

inline bool cmp(node a,node b){
	if(pos[a.id]==pos[b.id]){
		if(pos[a.id]&1)return a.r<b.r;
		return a.r>b.r;
	}
	return a.l<b.l;
}
inline void add(int x){
	sum+=(cnt[a[x]]<<1ll|1ll)*a[x];
	cnt[a[x]]++;
}
inline void del(int x){
	cnt[a[x]]--;
	sum-=(cnt[a[x]]<<1ll|1ll)*a[x];
}
int main(){
	read(n);read(q);
	block=n/sqrt(q*2/3)+1;
	for(int i=1;i<=n;i++)
		read(a[i]);
	for(int i=1;i<=q;i++){
		read(ask[i].l);
		read(ask[i].r);
		ask[i].id=i;
		pos[i]=(i-1)/block+1;
	}
	sort(ask+1,ask+1+q,cmp);
	l=1;r=0;
	for(int i=1;i<=q;i++){
		while(l>ask[i].l)add(--l);
		while(r<ask[i].r)add(++r);
		while(l<ask[i].l)del(l++);
		while(r>ask[i].r)del(r--);
		ans[ask[i].id]=sum;
	}
	for(int i=1;i<=q;i++){
		print(ans[i]);putchar('\n');
	}
	return 0;
}