题目链接 通过这个题，感受到了莫队的魔性。。。 限时5s的题，吸着氧，一路擦边4秒9，愣是怼完了所有样例，woc，nb。 这题莫起来很容易，虽然知道不是正解 ，从此爱上了莫队。。。 下面是ac代码：
#include <iostream> #include <cstring> #include <string> #include <cmath> #include <algorithm> #include <vector> #include <cstdio> #include <cstdlib> #include <map> #pragma GCC optimize(2) #define ll long long using namespace std; const int N = 2e5+5; ll c[N]; ll sum[N*5]; struct Node { ll l, r, id; }q[N]; ll anss[N]; ll block; ll ans = 0; int gg[N*10]; bool cmp(Node a, Node b) { return (a.r / block == b.r /block) ? a.l < b.l:a.r < b.r; } void del (int x) { sum[c[x]]--; ans += c[x] * (sum[c[x]]*sum[c[x]] - (sum[c[x]]+1)*(sum[c[x]]+1)); } void add(int x) { sum[c[x]]++; ans += c[x] * (sum[c[x]]*sum[c[x]] - (sum[c[x]]-1)*(sum[c[x]]-1)); } int main() { ll n, m, k; scanf("%lld%lld", &n, &m); block = sqrt(n); for (int i = 1; i <= n; i++) scanf("%lld", &c[i]); for (int i = 1; i <= m; i++) { scanf("%lld%lld", &q[i].l, &q[i].r); q[i].id = i; } sort(q+1, q+m+1, cmp); int l = 1, r = 0; for (int i = 1; i <= m; i++) { ll ql = q[i].l, qr = q[i].r; while(l < ql) del(l++); while(l > ql) add(--l); while(r < qr) add(++r); while(r > qr) del(r--); anss[q[i].id] = ans; } for (int i = 1; i <= m; i++) printf("%lld\n", anss[i]); return 0; }