看起来线段树之类的不好维护,但是移动区间的增量很好求,数据范围也能过,那么直接莫队就行了。
设加入或删除了值 \(x\),设原来区间内有 \(cnt_x\) 个,现在有 \(cnt'_x\) 个,那么增量就是 \(x((cnt'_x)^2-(cnt_x)^2)\),直接求就好了。
复杂度 \(O(t\sqrt n)\)。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 5, M = 1e6 + 5;
int n, m, sqn;
int cnt[M], a[N], blk[N];
ll answ[N];
struct node{int l, r, id;}q[N];
inline ll add(int x, int v)
{
ll now = 1ll * cnt[x] * cnt[x] * x;
cnt[x] += v;
ll now2 = 1ll * cnt[x] * cnt[x] * x;
return now2 - now;
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> n >> m;
sqn = pow(n, 0.6);
for(int i = 1; i <= n; i ++)
cin >> a[i], blk[i] = i / sqn;
for(int i = 1; i <= m; i ++)
{
int x, y;
cin >> x >> y;
q[i].l = x, q[i].r = y, q[i].id = i;
}
sort(q + 1, q + m + 1, [](node x, node y){
if(blk[x.l] == blk[y.l]) return x.r < y.r;
return blk[x.l] < blk[y.l];
});
int l = 1, r = 0, t = 0; ll ans = 0;
for(int i = 1; i <= m; i ++)
{
while(r < q[i].r) r ++, ans += add(a[r], 1);
while(l > q[i].l) l --, ans += add(a[l], 1);
while(r > q[i].r) ans += add(a[r], -1), r --;
while(l < q[i].l) ans += add(a[l], -1), l ++;
answ[q[i].id] = ans;
}
for(int i = 1; i <= m; i ++)
cout << answ[i] << "\n";
return 0;
}
标签:cnt,int,题解,ll,add,blk,ans,CF86D
From: https://www.cnblogs.com/adam01/p/18324198