1 #include<cstdio> 2 #include<cmath> 3 #include<algorithm> 4 using namespace std; 5 int Num,CH[12],f,c; 6 inline void R(int &x){ 7     c=0;f=1; 8     for(;c<‘0‘||c>‘9‘;c=getchar())if(c==‘-‘)f=-1; 9     for(x=0;c>=‘0‘&&c<=‘9‘;c=getchar())(x*=10)+=(c-‘0‘);10     x*=f;11 }12 inline void P(int x){13     if(x<10)putchar(x+‘0‘);14     else{P(x/10);putchar(x%10+‘0‘);}15 }16 int ans,anss[50001];17 int n,m,K,num[50001],a[50001],T[50001];18 int sqr(const int &x){return x*x;}19 struct ASK{int l,r,p;void Read(){R(l);R(r);}}Q[50001];20 bool operator < (const ASK &a,const ASK &b){return num[a.l]!=num[b.l] ? num[a.l]<num[b.l] : a.r<b.r;}21 void makeblock()22 {23     int sz=sqrt(n),sum=1; if(!sz) sz=1;24     for(;sum*sz<n;++sum)25       {26           int r=sum*sz;27           for(int i=sz*(sum-1)+1;i<=r;++i) num[i]=sum;28       }29     for(int i=sz*(sum-1)+1;i<=n;++i) num[i]=sum;30 }31 int main()32 {33     R(n);R(m);R(K);makeblock();34     for(int i=1;i<=n;++i) R(a[i]);35     for(int i=1;i<=m;++i) {Q[i].Read(); Q[i].p=i;}36     sort(Q+1,Q+m+1);37     for(int i=Q[1].l;i<=Q[1].r;++i){ans-=sqr(T[a[i]]);ans+=sqr(++T[a[i]]);}38     anss[Q[1].p]=ans;39     for(int i=2;i<=m;++i)40       {41           if(Q[i].l<Q[i-1].l){for(int j=Q[i-1].l-1;j>=Q[i].l;--j){ans-=sqr(T[a[j]]);ans+=sqr(++T[a[j]]);}}42           else{for(int j=Q[i-1].l;j<Q[i].l;++j){ans-=sqr(T[a[j]]);ans+=sqr(--T[a[j]]);}}43           if(Q[i].r<Q[i-1].r){for(int j=Q[i-1].r;j>Q[i].r;--j){ans-=sqr(T[a[j]]);ans+=sqr(--T[a[j]]);}}44           else{for(int j=Q[i-1].r+1;j<=Q[i].r;++j){ans-=sqr(T[a[j]]);ans+=sqr(++T[a[j]]);}}45         anss[Q[i].p]=ans;46       } for(int i=1;i<=m;++i) P(anss[i]),puts("");47     return 0;48 }