题目链接
https://www.luogu.org/problem/P2709
分析
莫队算法，每次区间调整根据次数变化前后的平方差更新答案
AC代码
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
inline int get_num() {
int num = 0;
char c = getchar();
while (c < '0' || c > '9') c = getchar();
while (c >= '0' && c <= '9')
num = num * 10 + c - '0', c = getchar();
return num;
}
const int maxn = 5e4 + 5;
struct Query {
int l, r, id, b;
bool operator < (const Query& rhs) const {
if (b == rhs.b) return r < rhs.r;
return b < rhs.b;
}
} q[maxn];
int a[maxn], c[maxn], ans[maxn];
int main() {
int n = get_num(), m = get_num(), k = get_num();
for (int i = 1; i <= n; ++i) a[i] = get_num();
int s = sqrt(n);
for (int i = 1; i <= m; ++i) {
q[i].l = get_num(), q[i].r = get_num();
q[i].id = i;
q[i].b = q[i].l / s;
}
sort(q + 1, q + m + 1);
int l = 1, r = 0, Ans = 0;
for (int i = 1; i <= m; ++i) {
while (l > q[i].l) ++c[a[--l]], Ans += 2 * c[a[l]] - 1;
while (r < q[i].r) ++c[a[++r]], Ans += 2 * c[a[r]] - 1;
while (l < q[i].l) --c[a[l]], Ans -= 2 * c[a[l++]] + 1;
while (r > q[i].r) --c[a[r]], Ans -= 2 * c[a[r--]] + 1;
ans[q[i].id] = Ans;
}
for (int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
return 0;
}
