CPPSET - Tập hợp động
Tác giả: skyvn97
Ngôn ngữ: C++
#include<cstdio>
#include<cassert>
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
const char no[]="no";
const int INF=(int)1e9+7;
struct node {
int val;
node *left,*right,*parent;
node(){}
node(const int &x) {
val=x;
left=NULL;
right=NULL;
parent=NULL;
}
bool isleft(const node *a) const {
return (left==a && a!=NULL);
}
bool isright(const node *a) const {
return (right==a && a!=NULL);
}
};
node *root;
void minimize(int &x,const int &y) {
if (x>y) x=y;
}
void maximize(int &x,const int &y) {
if (x<y) x=y;
}
void treeview(node *a,int lev) {
if (a==NULL) return;
FOR(i,1,lev) printf(" ");
printf("%d\n",a->val);
FOR(i,1,lev) printf(" ");
printf("left\n");
treeview(a->left,lev+1);
FOR(i,1,lev) printf(" ");
printf("right\n");
treeview(a->right,lev+1);
}
bool tree_empty(void) {
if (root==NULL) printf("empty\n");
return (root==NULL);
}
void tree_init(void) {
root=NULL;
}
void create(node *&a,const int &val) {
if (a!=NULL) return;
a=new node(val);
}
void link(node *a,node *b,int dir) {
//printf("Linking\n");
if (a==NULL) {
root=b;
if (root!=NULL) root->parent=NULL;
return;
}
if (dir==1) a->left=b; else a->right=b;
if (b!=NULL) b->parent=a;
//printf("Linked\n");
}
void left_rotation(node *a) {
assert(a!=NULL);
node *b,*c;
int dir=0;
c=a->parent;
if (c!=NULL) {
if (c->isleft(a)) dir=1; else dir=2;
}
b=a->right;
link(a,b->left,2);
link(b,a,1);
link(c,b,dir);
}
void right_rotation(node *a) {
assert(a!=NULL);
node *b,*c;
int dir=0;
c=a->parent;
if (c!=NULL) {
if (c->isleft(a)) dir=1; else dir=2;
}
b=a->left;
link(a,b->right,1);
link(b,a,2);
link(c,b,dir);
}
void splay(node *a) {
assert(a!=NULL);
//printf("Splay %d\n",a->val);
while (a->parent!=NULL) {
if (a->parent->parent==NULL) {
if (a->parent->isleft(a)) right_rotation(a->parent);
else left_rotation(a->parent);
}
else {
if (a->parent->isleft(a)) {
if (a->parent->parent->isleft(a->parent)) {
right_rotation(a->parent->parent);
right_rotation(a->parent);
}
else {
right_rotation(a->parent);
left_rotation(a->parent);
}
}
else {
if (a->parent->parent->isright(a->parent)) {
left_rotation(a->parent->parent);
left_rotation(a->parent);
}
else {
left_rotation(a->parent);
right_rotation(a->parent);
}
}
}
}
}
void find(const int &x) { //lower if not found
//printf("Find %d\n",x);
//if (root==NULL) printf("Tree empty\n");
node *p;
p=root;
if (p==NULL) return;
while (true) {
if (p->val==x) break;
if (p->val>x) {
if (p->left!=NULL) p=p->left;
else break;
}
else {
if (p->right!=NULL) p=p->right;
else break;
}
}
splay(p);
//treeview(root,0);
}
void split(const int &x,node *&a) { //a is root of greater node
//printf("Split\n");
//if (root==NULL) printf("Tree empty\n");
if (root==NULL) {
a=NULL;
return;
}
find(x);
a=root->right;
if (a!=NULL) a->parent=NULL;
root->right=NULL;
//treeview(root,0);
}
void merge(node *a) { // merge a to root, assume min(a)>max(root)
// printf("Merge\n");
// if (root==NULL) printf("Tree empty\n");
//if (a==NULL) printf("Merge NULL\n");
node *p;
p=root;
// if (p!=NULL) printf("%d\n",p->val);
if (p!=NULL) {
while (p->right!=NULL) p=p->right;
//printf("012\n");
splay(p);
}
// printf("123\n");
link(p,a,2);
// printf("234\n");
}
void insert(const int &x) {
node *p,*q;
int dir=0;
q=NULL;
p=root;
while (p!=NULL) {
q=p;
if (p->val==x) return;
if (p->val>x) {
p=p->left;
dir=1;
}
else {
p=p->right;
dir=2;
}
}
create(p,x);
link(q,p,dir);
splay(p);
}
void erase(const int &x) {
node *p,*nr;
//printf("erase %d\n",x);
//if (root==NULL) printf("Tree empty\n");
split(x,p);
//if (p!=NULL) printf("%d\n",p->val);
//if (root!=NULL) printf("%d\n",root->val);
if (root==NULL || root->val!=x) {
merge(p);
return;
}
nr=root->left;
delete (root);
root=nr;
link(NULL,root,1);
merge(p);
}
void minnode(void) {
if (tree_empty()) return;
node *p=root;
while (p->left!=NULL) p=p->left;
printf("%d\n",p->val);
splay(p);
}
void maxnode(void) {
if (tree_empty()) return;
node *p=root;
while (p->right!=NULL) p=p->right;
printf("%d\n",p->val);
splay(p);
}
void greater(const int &x) {
if (tree_empty()) return;
int res=INF;
node *p=root;
while (true) {
if (p->val>x) {
minimize(res,p->val);
if (p->left!=NULL) p=p->left;
else break;
}
else {
if (p->right!=NULL) p=p->right;
else break;
}
}
if (res<INF) printf("%d\n",res); else printf("%s\n",no);
splay(p);
}
void notless(const int &x) {
if (tree_empty()) return;
int res=INF;
node *p=root;
while (true) {
if (p->val>=x) {
minimize(res,p->val);
if (p->left!=NULL) p=p->left;
else break;
}
else {
if (p->right!=NULL) p=p->right;
else break;
}
}
if (res<INF) printf("%d\n",res); else printf("%s\n",no);
splay(p);
}
void less(const int &x) {
if (tree_empty()) return;
int res=-INF;
node *p=root;
while (true) {
if (p->val<x) {
maximize(res,p->val);
if (p->right!=NULL) p=p->right;
else break;
}
else {
if (p->left!=NULL) p=p->left;
else break;
}
}
if (res>-INF) printf("%d\n",res); else printf("%s\n",no);
splay(p);
}
void notgreater(const int &x) {
if (tree_empty()) return;
int res=-INF;
node *p=root;
while (true) {
if (p->val<=x) {
maximize(res,p->val);
if (p->right!=NULL) p=p->right;
else break;
}
else {
if (p->left!=NULL) p=p->left;
else break;
}
}
if (res>-INF) printf("%d\n",res); else printf("%s\n",no);
splay(p);
}
void answer(void) {
int t,v;
tree_init();
//int cnt=0;
while (true) {
scanf("%d",&t);
// cnt++;
if (t==0) return;
// printf("Query %d\n",cnt);
if ((t-3)*(t-4)!=0) scanf("%d",&v);
if (t==1) insert(v);
if (t==2) erase(v);
if (t==3) minnode();
if (t==4) maxnode();
if (t==5) greater(v);
if (t==6) notless(v);
if (t==7) less(v);
if (t==8) notgreater(v);
//treeview(root,0);
}
}
int main(void) {
#ifndef ONLINE_JUDGE
freopen("tmp.inp","r",stdin);
#endif
answer();
return 0;
}