[题解]小B的询问-莫队水题

这个题哇真的就是分块板子题
详见我这篇博客吧

然后我觉得有个细节可以注意下，一开始l要赋值为1,r赋值为0,这里改了蛮久才发现

#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>

const int N = 50000 + 30;

int n, m, k, blo, l, r, sum;
int a[N], id[N], s[N], Ans[N];

struct question
{
    int l, r, num;
} q[N];

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

int cmp(question x, question y)
{
    if (id[x.l] != id[y.l]) return id[x.l] < id[y.l];
    if (id[x.l] % 2 == 1) return x.r < y.r;
    else return x.r > y.r;
}

int main()
{
    n = read(); m = read(); k = read();
    blo = sqrt(n);
    for (int i = 1; i <= n; ++i) 
    {
        a[i] = read();
        id[i] = (i - 1) / blo + 1;
    }
    for (int i = 1; i <= m; ++i)
    {
        q[i].l = read();
        q[i].r = read();
        q[i].num = i; 
    }
    std::sort(q + 1, q + m + 1, cmp);
    l = 1; r = 0;
    for (int i = 1; i <= m; ++i)
    {
        while (l > q[i].l) --l, sum -= s[a[l]] * s[a[l]], s[a[l]]++, sum += s[a[l]] * s[a[l]];
        while (r < q[i].r) ++r, sum -= s[a[r]] * s[a[r]], s[a[r]]++, sum += s[a[r]] * s[a[r]];
        while (l < q[i].l) sum -= s[a[l]] * s[a[l]], s[a[l]]--, sum += s[a[l]] * s[a[l]], l++;
        while (r > q[i].r) sum -= s[a[r]] * s[a[r]], s[a[r]]--, sum += s[a[r]] * s[a[r]], r--;
        Ans[q[i].num] = sum;
    }
    for (int i = 1; i <= m; ++i) printf ("%d
", Ans[i]);
    return 0;
}