C++STL手写版

  1 #include<iostream>
  2 #include<cstdio>
  3 #define Red true
  4 #define Black false
  5 using namespace std;
  6 const int N=400005;
  7 int n;
  8 struct node{
  9     int key,si,we,co;
 10     node *f,*ch[2];
 11     void fill(int _key,int _co,int _we,node *now){//初始化节点信息
 12         this->key=_key;this->co=_co;
 13         this->si=this->we=_we; 
 14         this->f=this->ch[0]=this->ch[1]=now;
 15     }
 16     void pushup(){//上传更新
 17         this->si=this->ch[0]->si+this->ch[1]->si+this->we;
 18     }
 19     void pushdown(){//也是上传更新
 20         for(node *now=this;now->si;now=now->f) now->si--;
 21     }
 22     int getpos(int x){//判断向左或向右走
 23         return (this->key==x)?-1:(x>this->key);
 24     }
 25 }I;
 26 struct Red_Black_Tree{
 27     int cnt;
 28     node *rt,*nul;//红黑树没有空指针，所有空指针指向nul
 29     node pool[N],*tail,*re[N];//内存池
 30     void init(){//初始化
 31         cnt=0;tail=&pool[cnt];nul=tail++;
 32         nul->fill(0,Black,0,NULL);rt=nul;
 33     }
 34     node *New(int key){//新建节点
 35         node *now=nul;
 36         if(!cnt) now=tail++;
 37         else now=re[--cnt];
 38         now->fill(key,Red,1,nul);//新节点为红色
 39         return now;
 40     }
 41     void rotate(node *now,int pos){//旋转操作
 42         node *c=now->ch[pos^1];
 43         now->ch[pos^1]=c->ch[pos];
 44         if(c->ch[pos]->si) c->ch[pos]->f=now;
 45         c->f=now->f;
 46         if(!now->f->si) rt=c;//旋到根
 47         else now->f->ch[now->f->ch[0]!=now]=c;
 48         c->ch[pos]=now;now->f=c;c->si=now->si;
 49         now->pushup();
 50     }
 51     void insert_transfrom(node *now){//插入调整
 52         for(;now->f->co;){//当父亲为红色，不合法，需要调整
 53             node *fa=now->f,*gr=fa->f;
 54             int pos=fa==gr->ch[0];node *un=gr->ch[pos];
 55             if(un->co){//叔叔是红色，父亲和叔叔同时染成黑色
 56                 fa->co=un->co=Black;
 57                 gr->co=Red;now=gr;
 58             }
 59             else if(now==fa->ch[pos]) rotate(now=fa,pos^1);//父亲不是根
 60             else{
 61                 gr->co=Red;fa->co=Black;rotate(gr,pos);
 62             }
 63         }
 64         rt->co=Black;//根必须是黑色
 65     }
 66     void remove_transfrom(node *now){//删除调节
 67         for(;now!=rt&&!now->co;){
 68             int pos=now==now->f->ch[0];
 69             node *fa=now->f,*br=fa->ch[pos];
 70             if(br->co){//调节颜色一致
 71                 br->co=Black;fa->co=Red;
 72                 rotate(now->f,pos^1);
 73                 br=fa->ch[pos];
 74             }
 75             else if(!br->ch[0]->co&&!br->ch[1]->co){//兄弟的两个儿子都是黑色
 76                 br->co=Red;now=fa;//兄弟染成红色
 77             }
 78             else{
 79                 if(!br->ch[pos]->co){//保持路径上黑色节点数相同
 80                     br->ch[pos^1]->co=Black;br->co=Red;
 81                     rotate(br,pos);br=fa->ch[pos];
 82                 }
 83                 br->co=fa->co;br->ch[pos]->co=fa->co=Black;
 84                 rotate(fa,pos^1);break;
 85             }
 86         }
 87         now->co=Black;
 88     }
 89     void insert(int key){//插入节点
 90         node *now=rt,*fa=nul;int pos;
 91         for(;now->si;now=now->ch[pos]){
 92             now->si++;fa=now;
 93             pos=now->getpos(key);
 94             if(pos==-1){//找到对应值
 95                 now->we++;return;
 96             }
 97         }
 98         now=New(key);//找到位置，插入节点
 99         if(fa->si) fa->ch[key>fa->key]=now;
100         else rt=now;
101         now->f=fa;insert_transfrom(now);
102     }
103     node *find(node *now,int key){//查找位置
104         for(;now->si&&now->key!=key;now=now->ch[now->key<key]);
105         return now;
106     }
107     void remove(int key){
108         node *res=find(rt,key);
109         if(!res->si) return;//没有找到
110         if(res->we>1){//有多个，只删除一个
111             res->we--;res->pushdown();return;
112         }
113         node *fa=res,*now=nul;
114         if(res->ch[0]->si&&res->ch[1]->si){//有两个儿子，找节点替代自己
115             for(fa=res->ch[1];fa->ch[0]->si;fa=fa->ch[0]);//找后继
116         }
117         now=fa->ch[!fa->ch[0]->si];now->f=fa->f;
118         if(!fa->f->si) rt=now;//当前点是根
119         else fa->f->ch[fa->f->ch[1]==fa]=now;
120         if(res!=fa){
121             res->key=fa->key;res->we=fa->we;
122         }
123         fa->f->pushdown();
124         for(node *st=fa->f;fa->we>1&&st->si&&st!=res;st->si-=fa->we-1,st=st->f);
125         if(!fa->co) remove_transfrom(now);
126         re[cnt++]=fa;//回收内存
127     }
128     int rnk(int key){//查排名
129         int res,ans=0;
130         for(node *now=rt;now->si;){
131             res=now->ch[0]->si;
132             if(now->key==key) break;
133             else if(now->key>key) now=now->ch[0];
134             else{
135                 ans+=res+now->we;now=now->ch[1];
136             }
137         }
138         return ans+res+1;
139     }
140     int kth(int k){//查数
141         int res;node *now=rt;
142         for(;now->si;){
143             res=now->ch[0]->si;
144             if(k<=res) now=now->ch[0];
145             else if(res+1<=k&&k<=res+now->we) break;
146             else{
147                 k-=res+now->we;now=now->ch[1];
148             }
149         }
150         return now->key;
151     }
152     int pre(int key){//前驱
153         int res=0;
154         for(node *now=rt;now->si;){
155             if(now->key<key){
156                 res=now->key;now=now->ch[1];
157             }
158             else now=now->ch[0];
159         }
160         return res;
161     }
162     int nxt(int key){//后继
163         int res=0;
164         for(node *now=rt;now->si;){
165             if(now->key>key){
166                 res=now->key;now=now->ch[0];
167             }
168             else now=now->ch[1];
169         }
170         return res;
171     }
172 }rbt;
173 int main()
174 {
175     scanf("%d",&n);rbt.init();//初始化
176     for(int i=1;i<=n;i++){
177         int op,x;scanf("%d%d",&op,&x);
178         if(op==1) rbt.insert(x);
179         else if(op==2) rbt.remove(x);
180         else if(op==3) printf("%dn",rbt.rnk(x));
181         else if(op==4) printf("%dn",rbt.kth(x));
182         else if(op==5) printf("%dn",rbt.pre(x));
183         else printf("%dn",rbt.nxt(x));
184     }
185     return 0;
186 }