小象喜欢和数组玩。现在有一个数组a，含有n个正整数，记第i个数为ai
现在有m个询问，每个询问包含两个正整数lj和rj(1<=lj<=rj<=n)，小象想知道在Alj到Arj之中有多少个数x，其出现次数也为x
输入格式
第一行n和m，n表示数组大小，m表示询问个数，下一行为数组的值，再下m行，每行两个数lj和rj，描述如题面
输出格式
共m行，每行一个数，表示答案
题解：莫队
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5; int Hash[maxn], len; int pos[maxn], col[maxn], ans[maxn]; int n, m, ret; int cnt[maxn]; struct node { int l, r, id; }q[maxn]; bool cmp(node a, node b) { if (pos[a.l] != pos[b.l]) { return a.l < b.l; } if (pos[a.l] & 1) { return a.r > b.r; } return a.r < b.r; } void add(int x) { if (cnt[col[x]] == Hash[col[x]]) { ret--; } ++cnt[col[x]]; if (cnt[col[x]] == Hash[col[x]]) { ret++; } } void del(int x) { if (cnt[col[x]] == Hash[col[x]]) { ret--; } --cnt[col[x]]; if (cnt[col[x]] == Hash[col[x]]) { ret++; } } int main() { scanf("%d%d", &n, &m); int block = sqrt(n); for (int i = 1; i <= n; i++) { scanf("%d", &col[i]); Hash[++len] = col[i]; pos[i] = (i - 1) / block + 1; } sort (Hash + 1, Hash + len + 1); len = unique(Hash + 1, Hash + len + 1) - Hash - 1; for (int i = 1; i <= n; i++) { col[i] = lower_bound(Hash + 1, Hash + len + 1, col[i]) - Hash; } for (int i = 1; i <= m; i++) { scanf("%d%d", &q[i].l, &q[i].r); q[i].id = i; } sort (q + 1, q + m + 1, cmp); int l = 1, r = 0; for (int i = 1; i <= m; i++) { while(l < q[i].l) { del(l++); } while(r < q[i].r) { add(++r); } while(l > q[i].l) { add(--l); } while(r > q[i].r) { del(r--); } ans[q[i].id] = ret; } for (int i = 1; i <= m; i++) { printf("%d\n", ans[i]); } return 0; }
