luogu 2709 小B的询问 莫队

题目链接

Description

小B有一个序列，包含(N)个(1-K)之间的整数。他一共有(M)个询问，每个询问给定一个区间([L..R])，求(sum_{i=1}^{K}c_i^2)，其中(c_i)表示数字(i)在([L..R])中的重复次数。小B请你帮助他回答询问。

思路

裸的莫队。

(cnt[x])记录(x)的出现次数，增量为((cnt[x]+1)^2-cnt[x]^2=2*cnt[x]+1)或(-2*cnt[x]+1).

Code

#include <bits/stdc++.h>
#define F(i, a, b) for (int i = (a); i < (b); ++i)
#define F2(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i > (b); --i)
#define dF2(i, a, b) for (int i = (a); i >= (b); --i)
#define maxn 50010
using namespace std;
typedef long long LL;
struct node { int l, r,id; }a[maxn];
LL temp;
int n,m,k,blo,bl[maxn],v[maxn];
LL cnt[maxn],ans[maxn];
inline bool cmp(node&u, node& v) { return bl[u.l]<bl[v.l] || (bl[u.l]==bl[v.l]&&u.r<v.r); }
inline void upd(int x, int delta) { temp += delta*(cnt[x]<<1)+1; cnt[x]+=delta; }
int main() {
    scanf("%d%d%d", &n,&m,&k); blo = sqrt(n);
    F(i, 0, n) scanf("%d", &v[i]), bl[i]=i/blo;
    F(i, 0, m) {
        scanf("%d%d", &a[i].l, &a[i].r);
        --a[i].l, --a[i].r; a[i].id = i;
    }
    sort(a,a+m,cmp);
    int l=0, r=-1;
    temp=0;
    F(i, 0, m) {
        while (r<a[i].r) upd(v[++r],1);
        while (r>a[i].r) upd(v[r--],-1);
        while (l>a[i].l) upd(v[--l],1);
        while (l<a[i].l) upd(v[l++],-1);
        ans[a[i].id] = temp;
    }
    F(i, 0, m) printf("%lld
", ans[i]);
    return 0;
}