如题。

#include <math.h>
#include <stdio.h>
#include <algorithm>
static int len;
static long long ret;
long long res[100005];
int cnt[100005],a[100005];
class line
{
public:
	int l,r,id;
	line(int x=0,int y=0,int z=0):l(x),r(y),id(z)
	{}
	inline const bool operator<(const line &other)
	const{
		if((l-1)/len==(other.l-1)/len)
			return r<other.r;
		else
			return l/len<other.l/len;
	}
}e[100005];
inline void add(int x)
{
	ret+=2*cnt[x]+1;
	++cnt[x];
}
inline void del(int x)
{
	ret-=2*cnt[x]-1;
	--cnt[x];
}
int main()
{
	int i,l,r,n,m,k;
    l=r=0;
	scanf("%d %d %d",&n,&m,&k);
	len=int(sqrt(n));
	for(i=1;i<=n;++i)
		scanf("%d",a+i);
	for(i=1;i<=m;++i)
	{
		e[i].id=i;
		scanf("%d %d",&e[i].l,&e[i].r);
	}
	std::sort(e+1,e+m+1);
	for(i=1;i<=m;++i)
	{
		while(l>e[i].l)
			add(a[--l]);
		while(r<e[i].r)
			add(a[++r]);
		while(l<e[i].l)
			del(a[l++]);
		while(r>e[i].r)
			del(a[r--]);
		res[e[i].id]=ret;
	}
	for(i=1;i<=m;++i)
		printf("%lld\n",res[i]);
	return 0;
}