题解 CF220B 【Little Elephant and Array】

似乎莫队的思路更好想一些？ --- ### $Solution:$ 首先，$a_i> n$ 的 $a_i$ 肯定没有贡献，因为一共就只有 $n$ 个数。所以 $a_i > n$ 的都可以直接舍掉，这样子值域就也是 $10^5$ 了，无需离散化。 由于在此题是要恰好为 $a_i$ 次，所以 `Insert` 和 `Delete` 也要注意，一旦不是 $a_i$ 就要把贡献 $-1$。 比如说，在 `Insert` 的时候，当 `cnt[a[x]] == a[x] + 1` 时，贡献要减回来。`Delete` 也同理。 后面就是莫队基础操作了，时间复杂度为 $O(m\log m+n\sqrt{n})$。 --- ### $Code:$ ```cpp #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <queue> #include <vector> #include <cmath> using namespace std; #define ll long long #define fi first #define se second #define x1 x_csyakioi_1 #define x2 x_csyakioi_2 #define y1 y_csyakioi_1 #define y2 y_csyakioi_2 #define y0 y_csyakioi_0 #define dingyi int mid = l + r >> 1, ls = p << 1, rs = p << 1 | 1; inline int read(){ int x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); } return x * f; } const int N = 100010; int n, m, k, a[N], pos[N], cnt[N], ans[N], res; struct ask{ int l, r, idx; bool operator < (const ask&rhs)const{ return pos[l] ^ pos[rhs.l] ? l < rhs.l : pos[l] & 1 ? r < rhs.r : r > rhs.r; } }q[N]; inline void Insert(int x){ if(a[x] > n) return; ++cnt[a[x]]; if(cnt[a[x]] == a[x]) ++res; if(cnt[a[x]] == a[x] + 1) --res; } inline void Delete(int x){ if(a[x] > n) return; if(cnt[a[x]] == a[x] + 1) ++res; if(cnt[a[x]] == a[x]) --res; --cnt[a[x]]; } int main(){ n = read(); m = read(); k = sqrt(n); for(int i = 1; i <= n; ++i) a[i] = read(); for(int i = 1; i <= n; ++i) pos[i] = (i - 1) / k + 1; for(int i = 1; i <= m; ++i) q[i].l = read(), q[i].r = read(), q[i].idx = i; sort(q + 1, q + m + 1); int L = 1, R = 0; for(int i = 1; i <= m; ++i){ int x = q[i].l, y = q[i].r, idx = q[i].idx; while(R < y) Insert(++R); while(L > x) Insert(--L); while(R > y) Delete(R--); while(L < x) Delete(L++); ans[idx] = res; } for(int i = 1; i <= m; ++i) printf("%d\n", ans[i]); return 0; } ```