没有抄袭，自己打的。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=50005;

struct node{
	int l,r,id,pos;
	bool operator <(const node &x)const {
	if (pos==x.pos) return r<x.r;
	else return pos<x.pos; 
		}
}a[maxn];

int b[maxn],n,m,k,size,l=1,r;

ll cnt[maxn],ans[maxn],answer;

int main() {
	scanf("%d%d%d",&n,&m,&k);
	
	size=(int)sqrt(n);
	
	for(register int i=1;i<=n;i++)scanf("%d",&b[i]);
	
	for(register int i=1;i<=m;i++){
		scanf("%d%d",&a[i].l,&a[i].r);
		
		a[i].id=i;
		
		a[i].pos=(a[i].l-1)/size+1;
		
	}
	
	sort(a+1,a+n+1);
	
	for(register int i=1;i<=m;i++)
	{
		
		while(l>a[i].l) l--,cnt[b[l]]++,answer+=2 * cnt[b[l]] -1;
		
		while(r<a[i].r) r++,cnt[b[r]]++,answer+=2 * cnt[b[r]] -1;
		
		while(l<a[i].l) cnt[b[l]]--,answer-=2 * cnt[b[l]]+1, l++;
		
		while(r>a[i].r) cnt[b[r]]--,answer-=2 * cnt[b[r]]+1, r--;
		
		ans[a[i].id]=answer;
	}
	
	for(register int i=1;i<=m;i++) printf("%lld\n",ans[i]);
	
	return 0;
}