模板

莫队算法的核心就是分块+排序

变化的地方就在于四种操作的实现：

• Add(--L);
• Add(++R);
• Sub(L++);
• Sub(R--);

模板：P2709 小B的询问

每次询问 [l,r] 中每个数字出现次数的平方和，用 cnt 数组统计即可

莫队算法的优化：排序时，若块号相同，则根据块号的奇偶性排序（若为奇数块，则按 从小到大排序；否则按从大到小排序）

int a[N], pos[N], cnt[N], n, m, k;
struct Q {
    int l, r, id;
} q[N];
LL res[N], ans; // 维护全局变量 ans 记录当前已知区间

void add(int p)
{
    ans -= (LL)cnt[a[p]] * cnt[a[p]];
    cnt[a[p]] ++;
    ans += (LL)cnt[a[p]] * cnt[a[p]];
}

void sub(int p)
{
    ans -= (LL)cnt[a[p]] * cnt[a[p]];
    cnt[a[p]] --;
    ans += (LL)cnt[a[p]] * cnt[a[p]];
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    int sz = sqrt(n);
    for (int i = 1; i <= n; i++) 
    {
        scanf("%d", &a[i]);
        pos[i] = i / sz; // pos 可用 i / len 替代
    }
    for (int i = 0; i < m; i++)
    {
        scanf("%d%d", &q[i].l, &q[i].r);
        q[i].id = i;
    }
    // 排序 同一块内按右端点 否则按块号排
    sort(q, q + m, [](Q &x, Q &y)
    {
        return pos[x.l] == pos[y.l] ? x.r < y.r : pos[x.l] < pos[y.l];
    });
    int l = 1, r = 0; // 表示闭区间
    for (int 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 --);
        res[q[i].id] = ans;
    }
    for (int i = 0; i < m; i++) 
        printf("%lld\n", res[i]);
    return 0;
}

---

应用

https://codeforces.com/problemset/problem/220/B

求 [l,r] 中 cnt[x] == x 的个数，简单修改 cnt 为哈希表即可