这是我的，可以参考一下
```cpp
#include<bits/stdc++.h>
#include<cmath>
#define ll long long
using namespace std;
ll val[100010],t[100010],sum[100010],same=0;
ll kuai[100010];
struct node{
ll l,r,id,ans;
}a[100010];
int n,q,k;
ll read(){
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
bool cmp(node x,node y){
if(kuai[x.l]==kuai[y.l]){
if(kuai[x.l]&1) return x.r>y.r;
else return x.r<y.r;
}else return kuai[x.l]<kuai[y.l];
}
void jia(int i){
same=same-(t[val[i]]*t[val[i]])+((t[val[i]]+1)*(t[val[i]]+1));
t[val[i]]++;
}
void jian(int i){
same=same-(t[val[i]]*t[val[i]])+((t[val[i]]-1)*(t[val[i]]-1));
t[val[i]]--;
}
int main()
{
n=read(),q=read(),k=read();
int len=sqrt(n);
for(int i=1;i<=n;i++){
val[i]=read();
kuai[i]=(i-1)/len+1;
}
for(int i=1;i<=q;i++){
a[i].l=read();
a[i].r=read();
a[i].id=i;
}
sort(a+1,a+q+1,cmp);
for(int i=a[1].l;i<=a[1].r;i++){
same=same-(t[val[i]]*t[val[i]])+((t[val[i]]+1)*(t[val[i]]+1));
t[val[i]]++;
}
a[1].ans=same;
int nowl=a[1].l,nowr=a[1].r;
for(int i=2;i<=q;i++){
while(nowl<a[i].l){
jian(nowl);
nowl++;
}
while(nowl>a[i].l){
jia(nowl-1);
nowl--;
}
while(nowr<a[i].r){
jia(nowr+1);
nowr++;
}
while(nowr>a[i].r){
jian(nowr);
nowr--;
}
a[i].ans=same;
}
for(int i=1;i<=q;i++) sum[a[i].id]=a[i].ans;
for(int i=1;i<=q;i++) cout<<sum[i]<<endl;
return 0;
}
```
by gcx12012 @ 2023-04-28 11:59:09
@[Orange1015](/user/565378) 为啥用 map 存，不是开得下吗
by seanlsy @ 2023-04-28 12:41:38