题解 P1138 【第k小整数】

抱着我的Treap鏼鏼发抖emmm 这可是一道Treap吼题哇！ ```cpp #include <cstdio> #include <cstdlib> #define maxn (1 << 23) + 10 #define INF 0x3F3F3F3F bool used[maxn]; int siz = 0; int R() { int ret = 0; while(!ret || used[ret]) ret = rand() & 0x7FFFFF; return ret; } struct Node { int v, r, s, c; Node* ch[2]; Node(int v = 0); } null, *root = &null; Node::Node(int v): v(v), r(R()), s(0), c(0) {ch[0] = ch[1] = &null;} void maintain(Node* x) { x->s = x->ch[0]->s + x->ch[1]->s + x->c; } void rotate(Node* &x, int t) { Node* o = x->ch[t^1]; x->ch[t^1] = o->ch[t]; o->ch[t] = x; maintain(x); maintain(o); x = o; } void insert(Node* &x, int v) { if(x->v == v) { return; } int d; if(x == &null) x = new Node(v), x->s = 1, x->c = 1, siz++; else { insert(x->ch[d = v < x->v ? 0 : 1], v); if(x->ch[d]->r > x->r) rotate(x, d ^ 1); } maintain(x); return; } void remove(Node* &x, int v) { siz--; Node* u = x; if(x == &null) return; if(x->v == v) { if(x->c == 1) { if(x->ch[0] == &null) x = x->ch[1], delete u; else if(x->ch[1] == &null) x = x->ch[0], delete u; else { int d = x->ch[0]->r > x->ch[1]->r ? 1 : 0; rotate(x, d); remove(x->ch[d], v); } } else x->c--; } else remove(x->ch[v < x->v ? 0 : 1], v); if(x != &null) maintain(x); } int kth(Node* x, int k) { int l = x->ch[0]->s; if(k <= l) return kth(x->ch[0], k); else if(k > l + 1) return kth(x->ch[1], k - l - 1); else return x->v; } int rank(int v) { Node *x = root; int ret = 1; while(x != &null && x->v != v) { int ch = v < x->v ? 0 : 1; if(x->ch[ch] == &null) break; if(ch == 1) ret += x->s - x->ch[1]->s; x = x->ch[ch]; } ret += x->ch[0]->s; return ret; } int get(Node* x, int t) { while(x->ch[t] != &null) x = x->ch[t]; return x->v; } int ps(int v, int t) { Node *x = root, *las; while(x != &null && x->v != v) { int ch = v < x->v ? 0 : 1; if(ch == (t ^ 1)) las = x; x = x->ch[ch]; } if(x -> ch[t] != &null) return get(x->ch[t], t ^ 1); else return las->v; } int main() { srand(20180118); int n, k; scanf("%d%d", &n, &k); for(int i = 0; i < n; i++) { int v; scanf("%d", &v); insert(root, v); } if(k <= siz) printf("%d\n", kth(root, k)); else puts("NO RESULT"); return 0; } ```