洛谷【P2709】小B的询问(莫队)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 4e5 + 5;
ll a[maxn], pos[maxn], cnt[maxn];
struct node{ll l, r, k;}q[maxn];
ll ans[maxn], res;
ll n, m, k;

inline ll read(){
    ll s = 0, w = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}

inline void print(ll x){
    if(x < 0) x = ~x + 1, putchar('-');
    if(x > 9) print(x / 10);
    putchar(x % 10 + '0');
}

ll qpow(ll base, ll b){
    ll ret = 1;
    while(b){
        if(b & 1) ret *= base;
        base *= base;
        b >>= 1;
    }
    return ret;
}

void add(ll x){
    cnt[a[x]]++;
    res -= qpow(cnt[a[x]] - 1, 2);
    res += qpow(cnt[a[x]], 2);
}

void sub(ll x){
    cnt[a[x]]--;
    res -= qpow(cnt[a[x]] + 1, 2);
    res += qpow(cnt[a[x]], 2);
}

int main(){
    n = read(), m = read(), k = read();
    ll sz = sqrt(n);
    for(ll i = 1; i <= n; i++) a[i] = read(), pos[i] = i / sz;
    for(ll i = 0; i < m; i++) q[i].l = read(), q[i].r = read(), q[i].k = i;
    sort(q, q + m, [](node x, node y){return pos[x.l] == pos[y.l] ? x.r < y.r : pos[x.l] < pos[y.l];});
    ll l = 1, r = 0;
    for(ll i = 0; i < m; i++){
        while(q[i].l < l) add(--l);
        while(q[i].r > r) add(++r);
        while(q[i].l > l) sub(l++);
        while(q[i].r < r) sub(r--);
        ans[q[i].k] = res;
    }
    for(ll i = 0; i < m; i++)
        print(ans[i]), putchar('\n');

    return 0;
}