#include<bits/stdc++.h>
//#pragma GCC optimize(2)
#define ll long long

using namespace std;

const int N=50005;

ll Ans[N],ans;
int a[N],cnt[N],n,m,k,K;

struct node{
	int l,r,id;
}e[N];

inline bool cmp(node x,node y){
	if((x.l-1)/K==(y.l-1)/K) return x.r<y.r;
	return x.l/K<y.l/K;
}

inline void add(int x){
	ans+=2*cnt[x]+1;
	cnt[x]++;
}

inline void del(int x){
	ans-=2*cnt[x]-1;
	cnt[x]--;
}

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m>>k;
	int L,R,ans1=1,ans2=0;
	K=sqrt(n);
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=m;i++){
		cin>>e[i].l>>e[i].r;
		e[i].id=i;
	}
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;i++){
		L=e[i].l,R=e[i].r;
		while(ans1>L) ans1--,add(a[ans1]);
		while(ans2<R) ans2++,add(a[ans2]);
		while(ans1<L) del(a[ans1]),ans1++;
		while(ans2>R) del(a[ans2]),ans2--;
		Ans[e[i].id]=ans;
	}
	for(int i=1;i<=m;i++){
		cout<<Ans[i]<<'\n';
	}
	return 0;
}

上面代码 AC 了，但是老师说 add 和 del 里面应该是 cnt[a[x]] ，不是 cnt[x] ，为什么？