CF86D Powerful array

tony102

2020 年 11 月 21 日

1034 次浏览

暂无评论

509字数

题解

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

## 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 日