Loading... 因为太懒了被催更了所以更一篇莫队的题解 ## Sol 这就很经典 指针挪过去的时候把那个位置的数出现次数对答案的贡献先减掉,然后把个数加/减掉,在加上新的贡献 没了 我已经越来越一句话题解了 ## Code ```cpp #include <bits/stdc++.h> using namespace std; #define int long long const int SIZE = 1e6 + 5; int n, m, ans; int a[SIZE], cnt[SIZE], bel[SIZE], res[SIZE]; struct node { int l, r, idx; inline bool operator < (const node &a) const { return (bel[l] ^ bel[a.l]) ? bel[l] < bel[a.l] : (bel[l] & 1 ? r < a.r : r > a.r); } } q[SIZE]; namespace ae86 { const int bufl = 1 << 15; char buf[bufl], *s = buf, *t = buf; inline int fetch() { if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; } return *s++; } inline int read() { int a = 0, b = 1, c = fetch(); while (!isdigit(c))b ^= c == '-', c = fetch(); while (isdigit(c)) a = a * 10 + c - 48, c = fetch(); return b ? a : -a; } } using ae86::read; inline void modify(int pos) { ans -= a[pos] * (cnt[a[pos]] * cnt[a[pos]]); ++ cnt[a[pos]]; ans += a[pos] * (cnt[a[pos]] * cnt[a[pos]]); // ans += (cnt[a[pos]] * cnt[a[pos]]) * a[pos] + 2 * a[pos] * cnt[a[pos]] + a[pos]; } inline void del(int pos) { ans -= a[pos] * (cnt[a[pos]] * cnt[a[pos]]); -- cnt[a[pos]]; // ans += (cnt[a[pos]] * cnt[a[pos]]) * a[pos] + 2 * a[pos] * cnt[a[pos]] + a[pos]; ans += a[pos] * (cnt[a[pos]] * cnt[a[pos]]); } signed main() { // freopen("code.in", "r", stdin); // freopen("code.out", "w", stdout); n = read(), m = read(); for (int i = 1; i <= n; ++ i) a[i] = read(); int blockSiz = sqrt(n), blockCnt = ceil((double) n / blockSiz); for (int i = 1; i <= blockCnt; ++ i) { for (int j = (i - 1) * blockSiz; j <= i * blockSiz; ++ j) bel[j] = i; } for (int i = 1; i <= m; ++ i) q[i].l = read(), q[i].r = read(), q[i].idx = i; std::sort(q + 1, q + m + 1); int l = 1, r = 0; for (int i = 1; i <= m; ++ i) { while (l < q[i].l) del(l ++); while (l > q[i].l) modify(-- l); while (r < q[i].r) modify(++ r); while (r > q[i].r) del(r --); res[q[i].idx] = ans; } for (int i = 1; i <= m; ++ i) printf("%lld\n", res[i]); return 0; } ``` 最后修改:2021 年 09 月 04 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 如果觉得我的文章对你有用,请随意赞赏