求调

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5;
int n,m,k,a[N];
int pos[N],cnt[N];
long long res,ans[N];
struct Q{ 
    int l,r,k;
}q[N];
bool cmp(Q x,Q y){
    if(pos[x.l]==pos[y.l]){
        return x.r<y.r;
    }else{
        return x.l<y.l;
    }
}
void add(int x){
	cnt[a[x]]++;
    res+=cnt[a[x]]*cnt[a[x]]-(cnt[a[x]]-1)*(cnt[a[x]]-1);
}
void sub(int x){
    cnt[a[x]]--;
    res-=(cnt[a[x]]+1)*(cnt[a[x]]+1)-cnt[a[x]]*cnt[a[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++){
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].k=i; 
    }
    int siz=sqrt(n);
    for(int i=1;i<=n;i++){
        pos[i]=i/siz;
    } 
    sort(q+1,q+1+m,cmp);
    int l=1,r=0;
    for(int i=1;i<=m;i++){
        while(q[i].l<l) add(--l);
        while(q[i].r>r) add(++r);
        while(q[i].l>l) sub(l++);
        while(q[i].r<r) sub(r++);
        ans[q[i].k]=res;
    } 
    for(int i=1;i<=m;i++){
        printf("%lld\n",ans[i]);
    }
    return 0;
}