1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| #include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N = int(2E5) + 5;
const int MAX_Q = int(2E5) + 5;
const int MAX_S = int(1E6) + 5;
int n, t, a[MAX_N];
int bsz, bt, lb[MAX_N], rb[MAX_N], blk[MAX_N];
struct Query {
int l, r, id;
LL ans;
inline void input(int x) {
id = x; ans = 0;
scanf("%d%d", &l, &r);
}
inline friend bool operator < (const Query &u, const Query &v) {
if (blk[u.l] == blk[v.l]) return u.r < v.r;
else return blk[u.l] < blk[v.l];
}
} q[MAX_Q];
int cnt[MAX_S];
LL sum;
inline void add(int x) {
LL ori = 1LL * cnt[x] * cnt[x] * x;
++cnt[x];
LL tar = 1LL * cnt[x] * cnt[x] * x;
sum += (tar - ori);
}
inline void remove(int x) {
LL ori = 1LL * cnt[x] * cnt[x] * x;
--cnt[x];
LL tar = 1LL * cnt[x] * cnt[x] * x;
sum += (tar - ori);
}
int main() {
scanf("%d%d", &n, &t);
for (int i = 1; i <= n; ++i) scanf("%d", a + i);
for (int i = 1; i <= t; ++i) q[i].input(i);
bsz = int(sqrt(n));
int l, r;
for (l = 1; l <= n; l = r + 1) {
r = min(n, l + bsz - 1); ++bt;
lb[bt] = l; rb[bt] = r;
for (int i = l; i <= r; ++i) blk[i] = bt;
}
sort(q + 1, q + t + 1);
int curL = 0, curR = 0;
for (int i = 1; i <= t; ++i) {
while (curL < q[i].l) remove(a[curL]), ++curL;
while (curL > q[i].l) --curL, add(a[curL]);
while (curR < q[i].r) ++curR, add(a[curR]);
while (curR > q[i].r) remove(a[curR]), --curR;
q[i].ans = sum;
}
sort(q + 1, q + t + 1, [](const Query &u, const Query &v) { return u.id < v.id; });
for (int i = 1; i <= t; ++i) printf("%lld\n", q[i].ans);
return 0;
}
|