1 #include<cstdio> 2 #include<cctype> 3 #include<cmath> 4 #include<algorithm> 5 inline int getint() { 6     char ch; 7     while(!isdigit(ch=getchar())); 8     int x=ch^‘0‘; 9     while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^‘0‘);10     return x;11 }12 int base;13 struct Que {14     int l,r,id;15     bool operator < (const Que &x) const {16         return (r/base<x.r/base)?true:((r/base==x.r/base)?(l<x.l):false);17     }18 };19 const int K=50001;20 int cnt[K]={0},Ans=0;21 inline void inc(const int x) {22     Ans+=cnt[x]<<1|1;23     cnt[x]++;24 }25 inline void dec(const int x) {26     cnt[x]--;27     Ans-=cnt[x]<<1|1;28 }29 int main() {30     int n=getint(),m=getint();getint();31     base=(int)sqrt(n);32     int a[n];33     for(int i=0;i<n;i++) a[i]=getint();34     Que q[m];35     for(int i=0;i<m;i++) {36         q[i].l=getint()-1;37         q[i].r=getint()-1;38         q[i].id=i;39     }40     std::sort(&q[0],&q[m]);41     int ans[m];42     for(int i=0,l=0,r=-1;i<m;i++) {43         while(r<q[i].r) inc(a[++r]);44         while(r>q[i].r) dec(a[r--]);45         while(l<q[i].l) dec(a[l++]);46         while(l>q[i].l) inc(a[--l]);47         ans[q[i].id]=Ans;48     }49     for(int i=0;i<m;i++) printf("%d\n",ans[i]);50     return 0;51 }