因为太懒了被催更了所以更一篇莫队的题解
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;
}
Comments | NOTHING