不知道为啥我的莫队最终答案都得减一，然后还神秘 AC 了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int in(){
	char a = getchar();
	int k = 0, kk = 1;
	while(!isdigit(a)){
		if(a=='-') kk=-1;
		a=getchar();
	}
	while(isdigit(a)){
		k=(k<<3)+(k<<1)+a-'0', a= getchar();
	}
	return k*kk;
}
const int N = 5e4 + 5;
struct node{
	int l,r,p;
}e[N];
int cnt[N],kuai,L,R,n,m,k,a[N],ans,_ans[N];
bool cmp(node x,node y){
	return (x.l/kuai)==(y.l/kuai) ? x.r<y.r : x.l<y.l ;
}
void add(int pos){
	ans -= cnt[a[pos]]*cnt[a[pos]];
	cnt[a[pos]]++;
	ans += cnt[a[pos]]*cnt[a[pos]];
}
void del(int pos){
	ans -= cnt[a[pos]]*cnt[a[pos]];
	cnt[a[pos]]--;
	ans += cnt[a[pos]]*cnt[a[pos]];
}
signed main(){
	n=in(),m=in(),k=in();
	kuai = sqrt(n);
	for(int i=1;i<=n;i++) a[i] = in();
	for(int i=1;i<=m;i++){
		e[i].l = in(), e[i].r = in(), e[i].p = i;
	}
	sort(e+1,e+1+m,cmp);
	for(int i=1;i<=m;i++){
		int l = e[i].l, r = e[i].r, p = e[i].p;
		while(L<l) del(L++);
		while(L>l) add(--L);
		while(R>r) del(R--);
		while(R<r) add(++R);
		_ans[p] = ans; 
	}
	for(int i=1;i<=m;i++){
		cout << _ans[i]-1 << endl;// this
	}
	return 0;
}