Editorial for Tập hợp động
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
#include<iostream> #include<algorithm> #include<cstdio> #include<set> #define fr(a,b,c) for (a=b;a<=c;a++) using namespace std; set<int> a; set<int>::iterator it; int main() { int x,z; while (1) { scanf("%d",&z); if (!z) break; if (z<3 || z>4) scanf("%d",&x); if (z==1) a.insert(x); if (z==2) a.erase(x); if (z==3) { if (a.empty()) printf("empty\n"); else printf("%d\n",*a.begin()); } if (z==4) { if (a.empty()) printf("empty\n"); else printf("%d\n",*(--a.end())); } if (z==5) { if (a.empty()) printf("empty\n"); else { it=a.upper_bound(x); if (it==a.end()) printf("no\n"); else printf("%d\n",*it); } } if (z==6) { if (a.empty()) printf("empty\n"); else { it=a.lower_bound(x); if (it==a.end()) printf("no\n"); else printf("%d\n",*it); } } if (z==7) { if (a.empty()) printf("empty\n"); else { it=a.lower_bound(x); if (it==a.begin()) printf("no\n"); else printf("%d\n",*(--it)); } } if (z==8) { if (a.empty()) printf("empty\n"); else { it=a.upper_bound(x); if (it==a.begin()) printf("no\n"); else printf("%d\n",*(--it)); } } } return 0; }
Code mẫu của happyboy99x
#include <iostream> #include <cstdio> using namespace std; const int INF = (int) 1e9 + 7; class SplayTree { struct Node { Node * child[2], * parent; int key; } * root, * nil; void setChild(Node * x, Node * y, int d) { x->child[d] = y; y->parent = x; } int getDirection(Node * x, Node * y) { return x->child[0] == y ? 0 : 1; } void rotate(Node * x, int d) { Node * y = x->child[d]; Node * z = x->parent; setChild(x, y->child[d ^ 1], d); setChild(y, x, d ^ 1); setChild(z, y, getDirection(z, x)); } Node * splay(Node * x) { if(x == nil) return nil; while(x->parent != nil) { Node * y = x->parent; Node * z = y->parent; int dy = getDirection(y, x); int dz = getDirection(z, y); if(z == nil) { rotate(y, dy); } else if(dy == dz) { rotate(z, dz); rotate(y, dy); } else { rotate(y, dy); rotate(z, dz); } } return x; } Node * leftMost(Node * x) const { if(x == nil) return nil; while(x->child[0] != nil) x = x->child[0]; return x; } Node * rightMost(Node * x) const { if(x == nil) return nil; while(x->child[1] != nil) x = x->child[1]; return x; } public: SplayTree() { root = nil = new Node(); nil->child[0] = nil->child[1] = nil->parent = nil; nil->key = INF; } void insert(int key) { Node * curr = root; Node * last = nil; int dir = -1; while(curr != nil) { last = curr; if(key == curr->key) { root = splay(curr); return; } else if(key < curr->key) { curr = curr->child[0]; dir = 0; } else { curr = curr->child[1]; dir = 1; } } Node * u = new Node(); u->key = key; u->child[0] = u->child[1] = nil; setChild(last, u, dir); root = splay(u); } void erase(int key) { if(!contain(key)) return; Node * left = root->child[0]; Node * right = root->child[1]; left->parent = right->parent = nil; delete root; if(left == nil) { root = right; } else { left = splay(rightMost(left)); setChild(left, right, 1); root = left; } } bool isEmpty() const { return root == nil; } int minimum() { return (root = splay(leftMost(root)))->key; } int maximum() { return (root = splay(rightMost(root)))->key; } bool contain(int key) { Node * curr = root; while(curr != nil) { if(key == curr->key) { root = splay(curr); return true; } else if(key < curr->key) curr = curr->child[0]; else curr = curr->child[1]; } return false; } int greater(int x) { Node * curr = root; Node * res = nil; while(curr != nil) { if(x >= curr->key) { curr = curr->child[1]; } else { if(res == nil || curr->key < res->key) res = curr; curr = curr->child[0]; } } if(res != nil) root = splay(res); return res->key; } int smaller(int x) { Node * curr = root; Node * res = nil; while(curr != nil) { if(x <= curr->key) { curr = curr->child[0]; } else { if(res == nil || curr->key > res->key) res = curr; curr = curr->child[1]; } } if(res != nil) root = splay(res); return res->key; } }; int main() { ios::sync_with_stdio(false); cin.tie(NULL); SplayTree tree; for(int type, x; cin >> type, type != 0; ) { if(type != 3 && type != 4) cin >> x; if(type == 1) { tree.insert(x); } else if(type == 2) { tree.erase(x); } else if(tree.isEmpty()) { puts("empty"); } else if(type == 3) { printf("%d\n", tree.minimum()); } else if(type == 4) { printf("%d\n", tree.maximum()); } else if((type == 6 || type == 8) && tree.contain(x)) { printf("%d\n", x); } else { int res = type <= 6 ? tree.greater(x) : tree.smaller(x); if(res == INF) puts("no"); else printf("%d\n", res); } } return 0; }
Code mẫu của ladpro98
#include <bits/stdc++.h> #define ADD 1 #define DELETE 2 #define MINIMUM 3 #define MAXIMUM 4 #define SUCC 5 #define SUCC_2 6 #define PRED 7 #define PRED_2 8 using namespace std; set<int> S; int main() { set<int> :: iterator it; int kind, x; while (scanf("%d", &kind) == 1) { if (kind == 0) break; if (kind == ADD) { scanf("%d", &x); S.insert(x); } else if (kind == DELETE) { scanf("%d", &x); it = S.find(x); if (it != S.end()) S.erase(it); } else { if (S.empty()) {printf("empty\n"); continue;} if (kind == MINIMUM) { it = S.begin(); printf("%d\n", *it); } else if (kind == MAXIMUM) { it = S.end(); it--; printf("%d\n", *it); } else { scanf("%d", &x); if (kind == SUCC) it = S.upper_bound(x); else if (kind == SUCC_2) it = S.lower_bound(x); else if (kind == PRED) { it = S.lower_bound(x); it--; } else if (kind == PRED_2) { it = S.upper_bound(x); it--; } if (it == S.end()) printf("no\n"); else printf("%d\n", *it); } } } return 0; }
Code mẫu của RR
//Written by technolt #include <iostream> #include <algorithm> #include <cmath> #include <math.h> #include <stdio.h> #include <cstring> #include <vector> #include <map> #include <string> #include <set> #include <sstream> using namespace std; #define FOR(i,a,b) for(int i = a; i <= b; i++) #define DOWN(i,a,b) for(int i = a; i >= b; i--) #define FORV(i,a) for(typeof(a.begin()) i = a.begin(); i != a.end(); i++) #define doc(x); scanf("%d",&x); #define in(x) printf("%d\n",x) set <int > positive,negative; int main() { typeof(positive.begin()) it; while (1) { int command,x; doc(command); if (command==0) return 0; else if (command==1) { doc(x); positive.insert(x); negative.insert(-x); } else if (command==2) { doc(x); positive.erase(x); negative.erase(-x); } else if (command==3) { if (positive.empty()) printf("empty\n"); else { it=positive.begin(); in(*it); } } else if (command==4) { if (positive.empty()) printf("empty\n"); else { it=positive.end(); it--; in(*it); } } else if (command==5) { doc(x); if (positive.empty()) printf("empty\n"); else { it=positive.upper_bound(x); if (it==positive.end()) printf("no\n"); else in(*it); } } else if (command==6) { doc(x); if (positive.empty()) printf("empty\n"); else { it=positive.lower_bound(x); if (it==positive.end()) printf("no\n") ; else in(*it); } } else if (command==7) { doc(x); if (negative.empty()) printf("empty\n"); else { it=negative.upper_bound(-x); if (it==negative.end()) printf("no\n"); else in(-*it); } } else if (command==8) { doc(x); if (negative.empty()) printf("empty\n"); else { it=negative.lower_bound(-x); if (it==negative.end()) printf("no\n"); else in(-*it); } } } return 0; }
Code mẫu của hieult
#include <cstdio> #include <set> #include <iostream> //#include <conio.h> using namespace std; int main() { //freopen("CPPSET.in","r",stdin); set<int, less<int> > s,s1; set<int>::iterator it,it1; int thaotac,x; while(scanf("%d",&thaotac)>0 && thaotac>0) { if(thaotac == 1) { scanf("%d",&x); s.insert(x); s1.insert(-x); } else if(thaotac == 2) { scanf("%d",&x); it = s.find(x); it1 = s1.find(-x); if(it!=s.end()) { s.erase(it); s1.erase(it1); } } else if(thaotac == 3) { if(s.empty()) { printf("empty\n"); } else { it = s.begin(); printf("%d\n",*it); } } else if(thaotac == 4) { if(s.empty()) printf("empty\n"); else { it = s.end();it--; printf("%d\n",*it); } } else if(thaotac==5) { scanf("%d",&x); x; if(s.empty()) printf("empty\n"); else { it = s.upper_bound(x); if(it==s.end()) printf("no\n"); else printf("%d\n",*it); } } else if(thaotac==6) { scanf("%d",&x); if(s.empty()) printf("empty\n"); else { it = s.lower_bound(x); if(it==s.end()) printf("no\n"); else printf("%d\n",*it); } } else if(thaotac==7) { scanf("%d",&x); x = -x; if(s1.empty()) printf("empty\n"); else { it = s1.upper_bound(x); if(it==s1.end()) printf("no\n"); else printf("%d\n",-(*it)); } } else if(thaotac==8) { scanf("%d",&x); x = -x; if(s1.empty()) printf("empty\n"); else { it = s1.lower_bound(x); if(it==s1.end()) printf("no\n"); else printf("%d\n",-(*it)); } } } //getch(); }
Code mẫu của skyvn97
#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; }
Code mẫu của khuc_tuan
#include <iostream> #include <set> using namespace std; typedef set<int> :: iterator ite; set<int> se; int main() { while(true) { int code, x; //cout << " === "; //cout << "{"; //for(ite p=se.begin();p!=se.end();++p) //cout << "}"; scanf("%d", &code); if(code==0) break; if(code==1) { // add scanf("%d", &x); se.insert(x); } else if(code==2) { // delete scanf("%d", &x); se.erase(x); } else if(code==3) { // min if(se.size()!=0) printf("%d\n", *se.begin()); else printf("empty\n"); } else if(code==4) { // max if(se.size()==0) printf("empty\n"); else { ite i; i = se.end(); --i; printf("%d\n", *i); } } else if(code==5) { // succ scanf("%d", &x); if(se.size()==0) printf("empty\n"); else { ite i = se.upper_bound(x); if(i==se.end()) printf("no\n"); else printf("%d\n", *i); } } else if(code==6) { // succ_2 scanf("%d", &x); if(se.size()==0) printf("empty\n"); else { ite i = se.lower_bound(x); if(i==se.end()) printf("no\n"); else printf("%d\n", *i); } } else if(code==7) { // pred x scanf("%d", &x); if(se.size()==0) printf("empty\n"); else { ite i = se.lower_bound(x); if(i==se.end()) --i; while(i!=se.begin()) { if(*i<x) break; --i; } if(*i<x) printf("%d\n", *i); else printf("no\n"); } } else if(code==8) { scanf("%d", &x); if(se.size()==0) printf("empty\n"); else { ite i =se.lower_bound(x); if(i==se.end()) --i; while(i!=se.begin()) { if(*i<=x) break; --i; } if(*i<=x) printf("%d\n", *i); else printf("no\n"); } } } return 0; }
Comments