全部TLE，跟别人的代码对比了一下，蒟蒻感觉差不多，但是还是全部爆了QAQ。

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
	int x=0,f=1;char s=getchar();
	while (s>'9'||s<'0') {
		if (s=='-') f=-f;
		s=getchar();
	}
	while (s>='0'&&s<='9') {
		x=(x<<1)+(x<<3)+s-'0';
		s=getchar();
	}
	return x*f;
}
const int N = 1e5+10;
int n,m,k,t,l,r,now,a[N],num[N],ans[N];
struct node{
	int l,r,x,pos;
}q[N];
bool cmp(const node &a,const node &b) {
	if (a.pos==b.pos) return a.r<b.r;
	else return a.l<b.l;
}
signed main() {
	n=read();m=read();k=read();
	t=sqrt(n);
	for (int i=1;i<=n;++i) a[i]=read();
	for (int i=1;i<=m;++i) q[i].l=read(),q[i].r=read(),q[i].x=i,q[i].pos=(i-1)/t+1;
	sort(q+1,q+1+m,cmp);
	for (int i=q[1].l;i<=q[1].r;++i) {
		now-=num[a[i]]*num[a[i]];
		num[a[i]]++;
		now+=num[a[i]]*num[a[i]];
	}
	l=q[1].l;r=q[1].r;ans[q[1].x]=now;
	for (int i=2;i<=m;++i) {
		while (l>q[i].l) {
			l--;
			now+=num[a[l]]*2+1;
			num[a[l]]++;
		}
		while (l<q[i].l) {
			now-=num[a[l]]*num[a[l]];
			num[a[l]]--;
			now+=num[a[l]]*num[a[l]];
			l++;
		}
		while (r<q[i].r) {
			r++;
			now-=num[a[r]]*num[a[r]];
			num[a[r]]++;
			now+=num[a[r]]*num[a[r]];
		}
		while (r>q[i].r) {
			now-=num[a[r]]*num[a[r]];
			num[a[r]]--;
			now+=num[a[r]]*num[a[r]];
			r--;
		}
		ans[q[i].x]=now;
		l=q[i].l;r=q[i].r;
	}
	for (int i=1;i<=m;++i) printf("%lld\n",ans[i]);
	return 0;
}