题目链接 数列查找
考虑分块然后跑莫队，
设$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;
}