CF86D Powerful array

因为太懒了被催更了所以更一篇莫队的题解

Link

Sol

这就很经典

指针挪过去的时候把那个位置的数出现次数对答案的贡献先减掉,然后把个数加/减掉,在加上新的贡献

没了

我已经越来越一句话题解了

Code

#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;
}