0pts莫队求调

#include<bits/stdc++.h>
using namespace std;
#define Maxn 50005
#define int long long
struct query{
	int l,r,k;
}q[Maxn];
int n,m,k,lx=1,rx=0,a[Maxn];
int book[Maxn],bsize;
int res,ans[Maxn];
bool cmp(query x,query y){
	int u=book[x.l],v=book[y.l];
	if(u==v) return x.r<y.r;
	return u<v;
}
map<int,int> mp;
void Add(int x){
	res+=mp[x]*2+1;
	mp[x]++;
}
void Sub(int x){
	res-=mp[x]*2-1;
	mp[x]--;
}
inline int read()
{
	register int x = 0, f = 1;
	register char c = getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c<='9'&&c>='0'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
signed main(){
	n=read();
	m=read();
	k=read();
	bsize=sqrt(n);
	for(int i=1;i<=n;i++){
		a[i]=read();
		book[i]=i/bsize+1;
	}
	for(int i=0;i<m;i++){
		q[i].l=read();q[i].r=read();
		q[i].k=i;
	}
	sort(q,q+m,cmp);
	for(int i=0;i<m;i++){
		while(q[i].l<lx) Add(a[--lx]);
		while(q[i].r<rx) Sub(a[rx--]);
		while(q[i].l>lx) Sub(a[lx++]);
		while(q[i].r>rx) Add(a[++rx]);
		ans[q[i].k]=res;
	}
	for(int i=0;i<m;i++){
		printf("%d\n",ans[i]);
	}
	return 0;
}