题目描述
- 给定长度为 $n$ 的序列 $a$,有 $q$ 次询问,每次询问给出两个数 $l,r$。
- 对于每次询问,设 $cnt_i$ 表示 $i$ 在 $a_l,a_{l+1},\cdots,a_r$ 出现的次数,您需要求出 $\displaystyle\sum_i cnt_i^2\cdot i$。
- $1\le n,q\le 2\times 10^5$,$1\le a_i\le 10^6$,$1\le l\le r\le n$。
题解
莫队板子题。将所有查询区间读入,之后进行排序,这里要用到奇偶优化
如果左端点是奇数,右端点从大到小排,否则从小到大排
之后依次更新sum即可
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
ll a[N], cnt[N], ans[N];
ll sum, len;
int n, m, place[N];
struct node {
int id, l, r;
} q[N];
bool cmp(const node &x, const node &y) {
if (y.l / len == x.l / len) {
if ((y.l / len) & 1)
return y.r < x.r;
return y.r > x.r;
}
return y.l < x.l;
}
void add(int x) {
sum = sum - cnt[a[x]] * cnt[a[x]] * a[x];
cnt[a[x]]++;
sum = sum + cnt[a[x]] * cnt[a[x]] * a[x];
}
void del(int x) {
sum = sum - cnt[a[x]] * cnt[a[x]] * a[x];
cnt[a[x]]--;
sum = sum + cnt[a[x]] * cnt[a[x]] * a[x];
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
len = sqrt(n); // 分块
for (int i = 1; i <= n; i++) {
place[i] = i / len + 1;
}
for (int i = 1; i <= m; i++) {
cin >> q[i].l >> q[i].r;
q[i].id = i;
}
sort(q + 1, q + m + 1, cmp);
int j = 1, i = 0;
for (int k = 1; k <= m; k++) {
int l = q[k].l, r = q[k].r;
while (i < r)
add(++i);
while (i > r)
del(i--);
while (j < l)
del(j++);
while (j > l)
add(--j);
ans[q[k].id] = sum;
}
for (int i = 1; i <= m; i++) {
cout << ans[i] << endl;
}
return 0;
}