1 /************************************************************** 2     Problem: 3781 3     User: rausen 4     Language: C++ 5     Result: Accepted 6     Time:2212 ms 7     Memory:2380 kb 8 ****************************************************************/ 9  10 #include <cstdio>11 #include <cmath>12 #include <algorithm>13  14 using namespace std;15 typedef long long ll;16 const int N = 50005;17  18 int n, Q, c[N];19 int sz, pos[N];20 int l, r, cnt[N];21 ll sum, ans[N];22  23 struct query {24     int l, r, id;25      26     inline bool operator < (const query &b) const {27         return pos[l] == pos[b.l] ? r < b.r : pos[l] < pos[b.l];28     }29 } a[N];30  31 inline int read() {32     int x = 0;33     char ch = getchar();34     while (ch < ‘0‘ || ‘9‘ < ch)35         ch = getchar();36     while (‘0‘ <= ch && ch <= ‘9‘) {37         x = x * 10 + ch - ‘0‘;38         ch = getchar();39     }40     return x;41 }42  43 inline ll Sqr(int x) {44     return (ll) x * x;45 }46  47 inline void update(int x, int d) {48     sum -= (ll) Sqr(cnt[x]);49     cnt[x] += d;50     sum += (ll) Sqr(cnt[x]);51 }52  53 int main() {54     int i;55     n = read(), Q = read(), read();56     for (i = 1; i <= n; ++i)57         c[i] = read();58     sz = (int) sqrt(n);59     for (i = 1; i <= n; ++i)60         pos[i] = (i - 1) / sz + 1;61     for (i = 1; i <= Q; ++i)62         a[i].l = read(), a[i].r = read(), a[i].id = i;63     sort(a + 1, a + Q + 1);64     for (i = 1, l = 1, r = 0; i <= Q; ++i) {65         while (r < a[i].r) update(c[++r], 1);66         while (r > a[i].r) update(c[r--], -1);67         while (l > a[i].l) update(c[--l], 1);68         while (l < a[i].l) update(c[l++], -1);69         ans[a[i].id] = sum;70     }71     for (i = 1; i <= Q; ++i)72         printf("%lld\n", ans[i]);73     return 0;74 }