题目链接 数列查找
考虑分块然后跑莫队，
设$c[i]$为$i$在当前维护的区间内出现的次数，
$g[i]$为在当前维护的区间内有多少个数出现次数为$i$，
$bg[i]$把出现次数分块，$bg[i]$的意义是第$i$个块代表的所有出现次数中出现的个数。
$f[i][j]$对$1$到$n$分块，意义为当前在第$j$个数字块中有多少个数出现次数为$i$。
每一次询问的时候，我们先求出当前要求的出现次数是多少。
这个通过$bg[]$来求。
然后再根据$f[][]$确定当前区间中出现$k1$次的所有数中第$k2$小的数。
为了方便我用了离散化。
时间复杂度$O(m\sqrt{n} + n\sqrt{n})$
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i) #define MP make_pair #define fi first #define se second typedef long long LL; const int N = 4e4 + 10; const int M = 203; int belong[N]; int c[N], g[N], bg[N]; int f[N][M]; int l, r, kth; int blocknum; int L[M], R[M], ret[N]; struct node{ int l, r, x, y, id; void scan(){ scanf("%d%d%d%d", &l, &r, &x, &y); } friend bool operator < (const node &a, const node &b){ return belong[a.l] == belong[b.l] ? a.r < b.r : belong[a.l] < belong[b.l]; } } q[N]; int a[N], val[N]; int bs, cnt; int n, m; void remove(int x, int y){ --f[y][belong[x]]; if (g[y] == 1) --bg[belong[y]]; --g[y]; } void add(int x, int y){ ++f[y][belong[x]]; if (g[y] == 0) ++bg[belong[y]]; ++g[y]; } int solve(int i){ int num = 0; rep(j, 1, blocknum){ num += bg[j]; if (num >= q[i].x){ num -= bg[j]; rep(k, L[j], R[j]){ num += (int)(g[k] > 0); if (num == q[i].x) return k; } } } return 0; } int calc(int i, int x){ int num = 0; rep(j, 1, blocknum){ num += f[x][j]; if (num >= q[i].y){ num -= f[x][j]; rep(k, L[j], R[j]){ num += (int)(c[k] == x); if (num == q[i].y) return k; } } } return 0; } int main(){ scanf("%d", &n); rep(i, 1, n) scanf("%d", a + i), val[i] = a[i], q[i].id = i; sort(val + 1, val + n + 1); cnt = unique(val + 1, val + n + 1) - val - 1; rep(i, 1, n) a[i] = lower_bound(val + 1, val + cnt + 1, a[i]) - val; bs = sqrt(n); rep(i, 1, n) belong[i] = (i - 1) / bs + 1; blocknum = belong[n]; rep(i, 1, blocknum) L[i] = 1e9, R[i] = 0; rep(i, 1, n){ L[belong[i]] = min(L[belong[i]], i); R[belong[i]] = max(R[belong[i]], i); } scanf("%d", &m); rep(i, 1, m) q[i].scan(); sort(q + 1, q + m + 1); rep(i, 1, n) add(a[i], 0); l = 1, r = 0; rep(i, 1, m){ while (r < q[i].r){ ++r; remove(a[r], c[a[r]]); ++c[a[r]]; add(a[r], c[a[r]]); } while (r > q[i].r){ remove(a[r], c[a[r]]); --c[a[r]]; add(a[r], c[a[r]]); --r; } while (l > q[i].l){ --l; remove(a[l], c[a[l]]); ++c[a[l]]; add(a[l], c[a[l]]); } while (l < q[i].l){ remove(a[l], c[a[l]]); --c[a[l]]; add(a[l], c[a[l]]); ++l; } kth = solve(i); ret[q[i].id] = val[calc(i, kth)]; } rep(i, 1, m) printf("%d\n", ret[i]); return 0; }
转载于:https://www.cnblogs.com/cxhscst2/p/8437928.html
