1 #include <cmath> 2 #include <cstdio> 3 #include <iostream> 4 #include <algorithm> 5  6 const int MAXN = 50001; 7 int n, m, S, k, ans = 1; 8 int a[MAXN], ton[MAXN], anslist[MAXN]; 9 struct node10 {11     int l, r, id, num;12 }q[MAXN];13 14 inline int read()15 {16     int x = 0;17     char ch = getchar();18     for(; !isdigit(ch); ch = getchar());19     for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘;20     return x;21 }22 23 inline bool cmp(node x, node y)24 {25     return x.id ^ y.id ? x.id < y.id : x.r < y.r;26 }27 28 int main()29 {30     int i, x, y;31     n = read();32     m = read();33     k = read();34     S = sqrt(n);35     for(i = 1; i <= n; i++) a[i] = read();36     for(i = 1; i <= m; i++) q[i].l = read(), q[i].r = read(), q[i].num = i;37     for(i = 1; i <= m; i++) q[i].id = q[i].l / S + 1;38     std::sort(q + 1, q + m + 1, cmp);39     x = q[1].l, y = q[1].l;40     ton[a[x]]++;41     for(i = 1; i <= m; i++)42     {43         while(x < q[i].l)44         {45             ton[a[x]]--;46             ans -= ton[a[x]] << 1 | 1;47             x++;48         }49         while(x > q[i].l)50         {51             x--;52             ans += ton[a[x]] << 1 | 1;53             ton[a[x]]++;54         }55         while(y > q[i].r)56         {57             ton[a[y]]--;58             ans -= ton[a[y]] << 1 | 1;59             y--;60         }61         while(y < q[i].r)62         {63             y++;64             ans += ton[a[y]] << 1 | 1;65             ton[a[y]]++;66         }67         anslist[q[i].num] = ans;68     }69     for(i = 1; i <= m; i++) printf("%d\n", anslist[i]);70     return 0;71 }