洛谷 P1801 黑匣子_NOI导刊2010提高（06）
题目：
题解：
- 平衡树/对顶堆水题，以往的博客已经有对此类题目的详细讲解了。
#include #include #include #define N 200005#define inf 0x7fffffffusing namespace std;struct T {int l, r, val, dat, cnt, size;} t[N];int n, m, root, tot, pos = 1, now = 1;int a[N], b[N];int read(){ int x = 0, f = 1; char c = getchar(); while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();} return x *= f;}int New(int val){ t[++tot].val = val, t[tot].dat = rand(); t[tot].cnt = t[tot].size = 1; return tot;}void up(int p) {t[p].size = t[t[p].l].size + t[t[p].r].size + t[p].cnt;}void zig(int &y){ int x = t[y].l; t[y].l = t[x].r, t[x].r = y, y = x; up(t[y].r), up(y);}void zag(int &x){ int y = t[x].r; t[x].r = t[y].l, t[y].l = x, x = y; up(t[x].l), up(x);}void insert(int &p, int val){ if(!p) {p = New(val); return;} if(val == t[p].val) {t[p].cnt++, up(p); return;} if(val < t[p].val) { insert(t[p].l, val); if(t[t[p].l].dat > t[p].dat) zig(p); } else { insert(t[p].r, val); if(t[t[p].r].dat > t[p].dat) zag(p); } up(p);}int valOfRank(int p, int rank){ if(!p) return inf; if(t[t[p].l].size >= rank) return valOfRank(t[p].l, rank); if(t[t[p].l].size + t[p].cnt >= rank) return t[p].val; return valOfRank(t[p].r, rank - t[t[p].l].size - t[p].cnt);}int main(){ freopen("P1801.in", "r", stdin); freopen("P1801.out", "w", stdout); New(inf), New(-inf), t[1].l = 2, root = 1, up(1); n = read(), m = read(); for(int i = 1; i <= n; i++) a[i] = read(); for(int i = 1; i <= m; i++) b[i] = read(); for(int i = 1; i <= n; i++) { insert(root, a[i]); while(i == b[pos]) { printf("%d\n", valOfRank(root, now + 1)); pos++, now++; } } return 0;}