#pragma warning(disable:4996)
#include <iostream> #include <fstream> #include <algorithm> using namespace std; struct SplayTree { int data; int size, sum; SplayTree* prt, * lch, * rch; }; SplayTree* root, * now; int GetSize(SplayTree*); void Update(SplayTree*); SplayTree* RotateLeft(SplayTree*); SplayTree* RotateRight(SplayTree*); SplayTree* Merge(SplayTree*, SplayTree*); SplayTree* Splay(SplayTree*);
SplayTree* Insert(SplayTree*, SplayTree*, int); SplayTree* Delte(SplayTree*, int); int GetRank(SplayTree*, int); SplayTree* FindByRank(SplayTree*, int); SplayTree* FindPre(SplayTree*, int); SplayTree* FindNext(SplayTree*, int);
int main() { int n = 0, op, x; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d%d", &op, &x); SplayTree* temp = NULL; if (op == 1) { root = Insert(root, NULL, x); root = Splay(now); } else if (op == 2) { root = Delte(root, x); } else if (op == 3) { printf("%d\n", GetRank(root, x)); } else if (op == 4) { temp = FindByRank(root, x); root = Splay(temp); } else if (op == 5) { temp = FindPre(root, x); root = Splay(temp); } else if (op == 6) { temp = FindNext(root, x); root = Splay(temp); } if (op == 4 || op == 5 || op == 6) printf("%d\n", root->data); } return 0; } int GetSize(SplayTree* root) { if (root == NULL)return 0; return root->size; } void Update(SplayTree* root) { if (root == NULL)return; root->size = GetSize(root->lch) + GetSize(root->rch) + root->sum; } SplayTree* RotateLeft(SplayTree* y) { SplayTree* x = y->rch, * z = y->prt; if (z != NULL) { if (z->lch == y)z->lch = x; else z->rch = x; } y->rch = x->lch; if (x->lch != NULL)x->lch->prt = y; x->lch = y; y->prt = x; x->prt = z;
Update(y); Update(x); return x; } SplayTree* RotateRight(SplayTree* y) { SplayTree* x = y->lch, * z = y->prt; if (z != NULL) { if (z->lch == y)z->lch = x; else z->rch = x; } y->lch = x->rch; if (x->rch != NULL)x->rch->prt = y; x->rch = y; y->prt = x; x->prt = z;
Update(y); Update(x); return x; } SplayTree* Splay(SplayTree* x) { if (x == NULL)return NULL; while (x->prt != NULL) { SplayTree* y = x->prt, * z = x->prt->prt; if (z == NULL) { if (y->lch == x)x = RotateRight(x->prt); else x = RotateLeft(x->prt); } else { if (z->lch == y && y->lch == x) { x->prt = RotateRight(x->prt->prt); x = RotateRight(x->prt); } else if (z->rch == y && y->rch == x) { x->prt = RotateLeft(x->prt->prt); x = RotateLeft(x->prt); } else if (z->lch == y && y->rch == x) { x = RotateLeft(x->prt); x = RotateRight(x->prt); } else { x = RotateRight(x->prt); x = RotateLeft(x->prt); } } } return x; } SplayTree* Merge(SplayTree* left, SplayTree* right) { if (left == NULL)return right; if (right == NULL)return left; SplayTree* temp = left; while (temp->rch != NULL)temp = temp->rch; temp = Splay(temp); temp->rch = right; right->prt = temp; Update(temp); return temp; }
SplayTree* Insert(SplayTree* root, SplayTree* prt, int key) { if (root == NULL) { root = new SplayTree(); root->data = key; root->lch = NULL; root->rch = NULL; root->prt = prt; root->size = 1; root->sum = 1; now = root; return root; } else if (key == root->data) { root->sum++; root->size++; return root; } else if (key < root->data) { root->lch = Insert(root->lch, root, key); Update(root); } else { root->rch = Insert(root->rch, root, key); Update(root); } return root; } SplayTree* Delte(SplayTree* root, int key) { if (root == NULL) return NULL; while (root != NULL) { if (key < root->data)root = root->lch; else if (key > root->data)root = root->rch; else { root = Splay(root); root->sum--; root->size--; if (root->sum > 0)return root; SplayTree* left = root->lch, * right = root->rch; if (left != NULL)left->prt = NULL; if (right != NULL)right->prt = NULL; delete root; root = Merge(left, right); return root; } } return NULL; } int GetRank(SplayTree* root, int key) { if (root == NULL)return 0; if (key == root->data) return GetSize(root->lch) + 1; else if (key > root->data) return GetSize(root->lch) + root->sum + GetRank(root->rch, key); else return GetRank(root->lch, key); } SplayTree* FindByRank(SplayTree* root, int rank) { if (rank > GetSize(root->lch) + root->sum) return FindByRank(root->rch, rank - GetSize(root->lch) - root->sum); else if (rank > GetSize(root->lch)) return root; else return FindByRank(root->lch, rank); } SplayTree* FindPre(SplayTree* root, int key) { SplayTree* ans = NULL; while (root != NULL) { if (key <= root->data) { root = root->lch; } else { if (ans == NULL || ans->data < root->data)ans = root; root = root->rch; } } return ans; } SplayTree* FindNext(SplayTree* root, int key) { SplayTree* ans = NULL; while (root != NULL) { if (key < root->data) { if (ans == NULL || ans->data > root->data)ans = root; root = root->lch; } else { root = root->rch; } } return ans; }
|