记录一下莫队的模板
其他关于莫队的总结 https://www.luogu.com/article/er7hvyu3
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long ll;
int a[N],cnt[N];
int T;
ll res=0;
struct node{
int l,r,id;
bool operator<(const node& b)const{
if(l/T==b.l/T)return r<b.r;//如果在同一个块就按照右端点优先
return l<b.l;//如果不在同一个块则按照左端点优先
}
}nodes[N];
ll ans[N];
int n,m,k;
void add(int x){
res+=2*cnt[x]+1;
//原来的数量为cnt[x],现在变成cnt[x]+1,
//则总和增加(cnt[x]+1-cnt[x])*(cnt[x]+1+cnt[x])=2*cnt[x]+1;
cnt[x]++;
}
void sub(int x){
res-=2*cnt[x]-1;
cnt[x]--;
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=m;i++){
int l,r;
scanf("%d%d",&l,&r);
nodes[i]={l,r,i};
}
T=sqrt(n);
sort(nodes+1,nodes+m+1);
int l=1,r=0;//最初区间为空
for(int i=1;i<=m;i++){
while(r>nodes[i].r)sub(a[r--]);//减的时候要先减再移位
while(r<nodes[i].r)add(a[++r]);//加的时候要先移位再加
while(l>nodes[i].l)add(a[--l]);
while(l<nodes[i].l)sub(a[l++]);
ans[nodes[i].id]=res;//离线处理后,要恢复原来的询问顺序
}
for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);
return 0;
}