刷淼题

这题莫队不够优秀，需要离线还稍微难写点。

注意到一个数 x 可能对一个询问产生贡献的必要条件的是其出现过至少 x 次，这样的数不超过 $O(\sqrt{n})$ 个，对于每个这样的数记出现次数的前缀和，对于询问暴力枚举所有这样的数并通过前缀和查询该数的出现次数即可。

复杂度 $O((n+q)\sqrt{n})$ ，代码十分简单：

#include <cstdio>

struct { inline operator int () { int x; return scanf("%d", &x), x; } } read;

const int maxn = 100005, maxb = 500;
int a[maxn], tot[maxn];
int t[maxb][maxn], val[maxb];

int main () {
    int n = read, q = read;
    for (int i = 1; i <= n; i ++)
        if ((a[i] = read) <= n)
            ++ tot[a[i]];
    int p = 0;
    for (int x = 1; x <= n; x ++)
        if (tot[x] >= x) {
            val[++ p] = x;
            for (int i = 1; i <= n; i ++)
                t[p][i] = t[p][i - 1] + (a[i] == x);
        }
    while (q --) {
        int l = read, r = read, ans = 0;
        for (int i = 1; i <= p; i ++)
            if (t[i][r] - t[i][l - 1] == val[i])
                ++ ans;
        printf("%d\n", ans);
    }
}