题目链接&本文的的参考文献1
本文的参考文献2(这篇文章是xiezheyuan(洛谷的一个用户的用户名)的博客里的）
另外我还采纳了同学的一些意见。
这题主要的就是对一个静态的序列进行很多次的询问。在一定的方面上这些询问是可以相互转化得到的，并且可能有些被询问的区间之间还有重叠部分，于是我们就可能会想到用莫队写这题。另外，此题中,\(n\),\(m\)的最大值都还不是特别大，所以“莫队+分块”的时间复杂度应该是不会TLE的。
Talk is cheap ,show you the code .
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k,a[50005],cur,anss[50005];
struct node{
int l,r,id;
}q[50005];
int ans,cnt[50005];
bool cmp(node aa,node bb){
return aa.l/cur == bb.l/cur ? aa.r/cur < bb.r/cur : aa.l/cur < bb.l/cur;
}
int dx(int x){
return x*x;
}
void add(int x){
int y=dx(cnt[a[x]]);
++cnt[a[x]];
ans=ans+dx(cnt[a[x]])-y;
}
void del(int x){
int y=dx(cnt[a[x]]);
--cnt[a[x]];
ans=ans+dx(cnt[a[x]])-y;
}
signed main(){
std::ios::sync_with_stdio(false);
cin.tie();cout.tie();
cin>>n>>m>>k;
cur=(int)(sqrt(n));
for(int i=1;i<=n;++i)
cin>>a[i];
for(int i=1;i<=m;++i)
cin>>q[i].l>>q[i].r,q[i].id=i;
sort(q+1,q+m+1,cmp);
int l=1,r=0;
for(int i=1;i<=m;++i){
int ll=q[i].l,rr=q[i].r;
while(r>rr)
del(r--);
while(r<rr)
add(++r);
while(l<ll)
del(l++);
while(l>ll)
add(--l);
anss[q[i].id]=ans;
//cout<<l<<" "<<r<<endl;
//cout<<q[i].id<<" "<<ans<<endl;
}
for(int i=1;i<=m;++i)
cout<<anss[i]<<endl;
return 0;
}