思路

可以观察出，满足条件的 $x$ 的种数不会很多。假设种数为 $k$，由于总项数是 $n$，每种项数越少，种数越多，当 $x$ 取 $1 \sim k$ 时，每种项数最少，第 $i$ 种最少有 $i$ 项，因此总项数最少有 $\sum_{i = 1}^{k} i = \frac{k(k + 1)}{2} \le n$，解得种数 $k \le O(\sqrt n)$。

考虑 $x$ 的上界，当 $x > n$ 时，至少需要 $x > n$ 项它才满足条件，而数组只有 $n$ 项，因此 $x \le n$。

升序统计出每个 $x$ 出现的所有下标放到数组 $p[x]$，统计出个数大于等于 $x$ 的所有 $x$ 放到数组 $a$。对于每个查询，遍历 $a$，对于 $a$ 中的每个 $x$，在 $p[x]$ 中找到大于等于 $l$ 的最小下标 $p$，小于等于 $r$ 的最大下标 $q$，则 $q - p + 1$ 就是 $x$ 在 $[l, r]$ 内出现的次数。

时间复杂度 $O(m \sqrt n logn)$，计算量 $5e8$。

#include <iostream>
#include <vector>
#include <algorithm>

#define endl "\n"

using namespace std;

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, m;
  cin >> n >> m;
  vector<vector<int>> p(n + 1);
  for (int i = 1, x; i <= n; i++) {
    cin >> x;
    if (x <= n) p[x].push_back(i);
  }
  vector<int> a;
  for (int x = 1; x <= n; x++)
    if (p[x].size() >= x) a.push_back(x);

  while (m--) {
    int l, r;
    cin >> l >> r;
    int cnt = 0;
    for (auto x : a)
      cnt += (upper_bound(p[x].begin(), p[x].end(), r)
           -  lower_bound(p[x].begin(), p[x].end(), l)) == x;
    cout << cnt << endl;
  }

  return 0;
}