题意

给定一个数组 $A$，有多个查询 $[l, r]$，需要判断每个查询区间内是否存在一个数值 $x$，使得该数值在区间内恰好出现 $x$ 次。

思路

本题可以用更简单的 $O(N \sqrt{N})$ 解法，但这里将介绍一种 $O(N \log N)$ 的离线算法。
我们将所有查询离线处理。对于每个右端点 $x$（$0 \le x < n$），记录所有以 $x$ 结尾的查询。然后从左到右遍历 $x$，同时维护一个数组 $D$，使得对于当前 $x$，$D_l + D_{l+1} + \dots + D_x$ 就是查询 $[l, x]$ 的答案。
为了保持 $D$ 的正确性，在处理所有以 $x$ 结尾的查询之前，需要先更新 $D$。设当前数值 $t = A_x$，并设向量 $P$ 为数值 $t$ 之前出现位置的下标列表（下标从 $0$ 开始）。

• 如果 $|P| \ge t$，则需要在 $D_{P[|P|-t]}$ 上加 $1$，因为这个位置是从右往左第一个恰好包含 $t$ 个 $t$ 的位置。
• 之后，如果 $|P| > t$，则需要在 $D_{P[|P|-t-1]}$ 上减 $2$，以关闭当前区间并取消之前的贡献。
• 最后，如果 $|P| > t+1$，则还需要在 $D_{P[|P|-t-2]}$ 上加 $1$，以取消之前对区间的关闭操作。

算法步骤

1. 将所有查询按右端点 $r$ 分组，存入列表。
2. 初始化数组 $D$ 全为 $0$，并初始化每个数值的出现位置列表 $P$ 为空。
3. 从左到右遍历 $x$ 从 $0$ 到 $n-1$：
   • 设 $t = A_x$，将 $x$ 加入 $t$ 对应的位置列表 $P$。
   • 根据上述规则更新 $D$ 数组：
     • 若 $|P| \ge t$，则 $D_{P[|P|-t]} \leftarrow D_{P[|P|-t]} + 1$。
     • 若 $|P| > t$，则 $D_{P[|P|-t-1]} \leftarrow D_{P[|P|-t-1]} - 2$。
     • 若 $|P| > t+1$，则 $D_{P[|P|-t-2]} \leftarrow D_{P[|P|-t-2]} + 1$。
   • 对于所有以 $x$ 为右端点的查询 $[l, x]$，计算 $D_l + D_{l+1} + \dots + D_x$ 作为答案。
4. 输出所有查询的答案。

复杂度分析

• 时间复杂度：$O(N \log N)$，其中 $N$ 为数组长度。每次更新 $D$ 和查询区间和均可用树状数组或线段树实现 $O(\log N)$ 操作。
• 空间复杂度：$O(N)$，用于存储 $D$ 数组、位置列表和查询分组。

代码说明

• 使用树状数组（Fenwick Tree）维护 $D$ 的区间和，支持单点更新和前缀和查询。
• 遍历 $x$ 时，对每个数值 $t$ 维护其出现位置列表，按上述规则进行三次更新。
• 对于每个查询 $[l, x]$，通过树状数组计算 $sum(x) - sum(l-1)$ 得到答案。

#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);
	}
}