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.

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

Please read the guidelines before commenting.


There are no comments at the moment.