[题解]LuoGu1801：黑匣子_NOI导刊2010提高（06）

原题传送门
虽说是堆题&＃xff0c;但也可以用主席树不是&＃xff1f;
对于每个要get的地方&＃xff0c;相当于询问区间为[1,x]&＃xff0c;其实就是模板题啦

Code&＃xff1a;

#include
#define maxn 200010
using namespace std;
int lc[maxn << 5], rc[maxn << 5], sum[maxn << 5], rt[maxn], sz;
int n, m, a[maxn], b[maxn], p, q;inline int read(){int s &＃61; 0, w &＃61; 1;char c &＃61; getchar();for (; !isdigit(c); c &＃61; getchar()) if (c &＃61;&＃61; &＃39;-&＃39;) w &＃61; -1;for (; isdigit(c); c &＃61; getchar()) s &＃61; (s << 1) &＃43; (s << 3) &＃43; (c ^ 48);return s * w;
}void build(int &rt, int l, int r){rt &＃61; &＃43;&＃43;sz, sum[rt] &＃61; 0;if (l &＃61;&＃61; r) return;int mid &＃61; (l &＃43; r) >> 1;build(lc[rt], l, mid); build(rc[rt], mid &＃43; 1, r);
}int update(int o, int l, int r){int oo &＃61; &＃43;&＃43;sz;lc[oo] &＃61; lc[o], rc[oo] &＃61; rc[o], sum[oo] &＃61; sum[o] &＃43; 1;if (l &＃61;&＃61; r) return oo;int mid &＃61; (l &＃43; r) >> 1;if (mid >&＃61; p) lc[oo] &＃61; update(lc[o], l, mid); else rc[oo] &＃61; update(rc[o], mid &＃43; 1, r);return oo;
}int query(int u, int v, int l, int r, int k){int mid &＃61; (l &＃43; r) >> 1, x &＃61; sum[lc[v]] - sum[lc[u]];if (l &＃61;&＃61; r) return l;if (x >&＃61; k) return query(lc[u], lc[v], l, mid, k); else return query(rc[u], rc[v], mid &＃43; 1, r, k - x);
}int main(){n &＃61; read(), m &＃61; read();for (int i &＃61; 1; i <&＃61; n; &＃43;&＃43;i) a[i] &＃61; read(), b[i] &＃61; a[i];sort(b &＃43; 1, b &＃43; 1 &＃43; n);q &＃61; unique(b &＃43; 1, b &＃43; 1 &＃43; n) - b - 1;build(rt[0], 1, q);for (int i &＃61; 1; i <&＃61; n; &＃43;&＃43;i){p &＃61; lower_bound(b &＃43; 1, b &＃43; 1 &＃43; q, a[i]) - b;rt[i] &＃61; update(rt[i - 1], 1, q);}int k &＃61; 0;for (int i &＃61; 1; i <&＃61; m; &＃43;&＃43;i){int x &＃61; read();printf("%d\n", b[query(rt[0], rt[x], 1, q, &＃43;&＃43;k)]);}return 0;
}