题目链接:https://www.luogu.org/problemnew/show/P2709
求(cnt表示a[i]出现的次数),ans = (cnt[a[i]] + 1) ^2 - (cnt[a[i]]^2)
(把add,del单独写成两个函数，转移过程用位运算会更快一点)
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <map> #include <set> #include <vector> #include <string> #include <cmath> #define rep(i, s, e) for(int i = s; i < e; ++i) #define P pair<int, int> #define INF 0x3f3f3f3f using namespace std; typedef long long ll; static const int MAX_N = 5e4 + 5; static const ll Mod = 1e9 + 7; struct Query{ int l, r, id, pos; bool operator < (Query &q)const{ if(pos == q.pos) return r < q.r; return pos < q.pos; } }q[MAX_N]; ll rev[MAX_N]; int cnt[MAX_N], a[MAX_N]; ll ans; void update(int p, int v){ ans -= cnt[a[p]] * cnt[a[p]]; cnt[a[p]] += v; ans += cnt[a[p]] * cnt[a[p]]; } void solve(){ int n, m, k; scanf("%d%d%d", &n, &m, &k); for(int i = 1; i <= n; ++i) scanf("%d", &a[i]); int block = (int)sqrt(n); for(int i = 1; i <= m; ++i){ scanf("%d%d", &q[i].l, &q[i].r); q[i].id = i; q[i].pos = (q[i].l - 1) / block + 1; } sort(q + 1, q + m + 1); int l = 1, r = 0; for(int i = 1; i <= m; ++i){ while(l < q[i].l) update(l++, -1); while(l > q[i].l) update(--l, 1); while(r < q[i].r) update(++r, 1); while(r > q[i].r) update(r--, -1); rev[q[i].id] = ans; } for(int i = 1; i <= m; ++i) printf("%lld\n", rev[i]); } int main(){ // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); solve(); return 0; }
