题目链接

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\n", ans[i]);

    return 0;

}