题意：给出一段序列，再给出m个查询区间，求区间内有多少个x，使得x等于x的出现次数。
题解：前缀和 这道题还可以用莫队或者线段树来求，不是很会。
若要值等于出现次数，那么这个值必须小于等于n，这是一次剪枝。 我们存储左右区间端点，离线查询。
遍历1-n的所有元素，只有该元素个数大于其值，才进行下列操作，第二次剪枝。 对于该元素，记录其前缀和，这样就可以用sum[r[j]] - sum[l[j] - 1]表示区间内该元素个数，若等于其值，++即可。
#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<queue> #include<stack> #include<cmath> #include<vector> #include<fstream> #include<set> #include<map> #include<sstream> #include<iomanip> #define ll long long using namespace std; const int maxn = 1e5 + 5; int n, m, a[maxn], cnt[maxn], l[maxn], r[maxn], sum[maxn], ans[maxn]; int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); if (a[i] <= n) cnt[a[i]]++; } for (int i = 1; i <= m; i++) scanf("%d%d", &l[i], &r[i]); for (int i = 1; i <= n; i++) { if (cnt[i] >= i) { for (int j = 1; j <= n; j++) sum[j] = sum[j - 1] + (a[j] == i); for (int j = 1; j <= m; j++) { if (sum[r[j]] - sum[l[j] - 1] == i) ans[j]++; } } } for (int j = 1; j <= m; j++) { printf("%d\n", ans[j]); } return 0; }