COJS：1829. [Tyvj 1728]普通平衡树-白红宇

COJS：1829. [Tyvj 1728]普通平衡树

阅读量：5971 次

发布时间：2019-06-19

本文共 11749 字，大约阅读时间需要 39 分钟。

　　　　　　　　　　　　　　　　★★★ 输入文件：phs.in 输出文件：phs.out 简单对比

　　　　　　　　　　　　　　　　　　时间限制：1 s 内存限制：128 MB

【题目描述】

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

1. 插入x数

2. 删除x数(若有多个相同的数，因只删除一个)

3. 查询x数的排名(若有多个相同的数，因输出最小的排名)

4. 查询排名为x的数

5. 求x的前驱(前驱定义为小于x，且最大的数)

6. 求x的后继(后继定义为大于x，且最小的数)

【输入格式】

第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6)

【输出格式】

对于操作3,4,5,6每行输出一个数，表示对应答案

【样例输入】

101 1064654 11 3177211 4609291 6449851 841851 898516 819681 4927375 493598

【样例输出】

10646584185492737

【提示】

1.n的数据范围：n<=100000

2.每个数的数据范围：[-1e7,1e7]

　　SBT版的：

1 #include
       
          2 using namespace std;  3 const int maxn=100010;  4 int root,tot,N;  5 int key[maxn],siz[maxn],lc[maxn],rc[maxn];  6 void r_rotate(int &rt){  7     int k=lc[rt];  8     lc[rt]=rc[k];  9     rc[k]=rt; 10     siz[k]=siz[rt]; 11     siz[rt]=siz[lc[rt]]+siz[rc[rt]]+1; 12     rt=k; 13 }   14 void l_rotate(int &rt){ 15     int k=rc[rt]; 16     rc[rt]=lc[k]; 17     lc[k]=rt; 18     siz[k]=siz[rt]; 19     siz[rt]=siz[lc[rt]]+siz[rc[rt]]+1; 20     rt=k; 21 } 22 void MAINTAIN(int &rt,bool flag){ 23     if(flag==false){
     //rt的左子树的某子树>rt的右子树  24         if(siz[lc[lc[rt]]]>siz[rc[rt]]) r_rotate(rt);//如果rt的左孩子的左孩子>rt的右孩子，rt右旋  25         else if(siz[rc[lc[rt]]]>siz[rc[rt]]){
     //如果rt的左孩子L的右孩子B > rt的右孩子R：  26             l_rotate(lc[rt]);//先让rt的左孩子左旋，使rt的左子树变成以B为根  27             r_rotate(rt);//再右旋再变成以B为根  28         } 29         else return;//平衡  30     } 31     else{
     //rt的右子树的某子树>rt的左子树  32         if(siz[rc[rc[rt]]]>siz[lc[rt]]) l_rotate(rt); 33         else if(siz[lc[rc[rt]]]>siz[lc[rt]]){ 34             r_rotate(rc[rt]); 35             l_rotate(rt); 36         } 37         else return; 38     } 39     MAINTAIN(lc[rt],0); MAINTAIN(rc[rt],1);//检查是否满足平衡  40     MAINTAIN(rt,1); MAINTAIN(rt,0); 41 } 42 void insert(int &rt,int v){ 43     if(rt==0){
     //找到合适的位置插入  44         rt=++tot;  45         key[rt]=v; 46         lc[rt]=rc[rt]=0; siz[rt]=1; 47         return ; 48     } 49     siz[rt]++; 50     if(v<=key[rt]) insert(lc[rt],v); 51     else insert(rc[rt],v); 52     MAINTAIN(rt,v>key[rt]);//调整树结构  53 } 54 int Delete(int &rt,int v){ 55     int ans; 56     siz[rt]--; 57     if(v==key[rt]||(v
        
         key[rt]&&rc[rt]==0)){ 58         ans=key[rt]; 59         if(lc[rt]==0||rc[rt]==0) rt=lc[rt]+rc[rt];//没有左子树或者右子树，直接利用&操作，相当于直接以子树接到上个节点  60         else key[rt]=Delete(lc[rt],key[rt]+1);//返回左子树中的最大值，然后替换当前的rt，相当于删掉当前节点，用左子树中最大值放在这个位置来代替 61         return ans; 62     } 63     if(v
         
          key[rt]) return find(rc[rt],v); 72 } 73 int rank(int &rt,int v){
     //询问排名  74     if(rt==0) return 1; 75     if(v<=key[rt]) return rank(lc[rt],v); 76     else return siz[lc[rt]]+1+rank(rc[rt],v); 77 } 78 /* 79 如果元素唯一的话，可以这么写：  80 int rank(int &rt,int v){ 81     if(rt==0) return 1; 82     if(v==key[rt]) return siz[lc[rt]]+1; 83     if(v
          
           v 必然要往更小的方向，即rt的左子树  96     else{
     //此时 key[rt]
           
            =key[rt]) return succ(rc[rt],v);105     else{106         int ans=succ(lc[rt],v);107         if(ans==v) return key[rt];108         return ans;109     }110 }111 void inorder(int rt){
     //输出中序遍历 112     if(rt!=0){113         inorder(lc[rt]);114         cout<
            
             <<" ";115 inorder(rc[rt]);116 }117 }118 int main(){ 119 siz[0]=root=tot=0;120 scanf("%d",&N);121 for(int i=1,kin,num;i<=N;i++){122 scanf("%d%d",&kin,&num);123 if(kin==1) insert(root,num);124 else if(kin==2) Delete(root,num);125 else if(kin==3) printf("%d\n",rank(root,num));126 else if(kin==4) printf("%d\n",select(root,num));127 else if(kin==5) printf("%d\n",pred(root,num));128 else if(kin==6) printf("%d\n",succ(root,num));129 }130 return 0;131 }

无注释版的：

1 #include
       
          2 using namespace std;  3 const int maxn=100010;  4 int root,tot,N;  5 int key[maxn],siz[maxn],lc[maxn],rc[maxn];  6 void r_rotate(int &rt){  7     int k=lc[rt];  8     lc[rt]=rc[k];  9     rc[k]=rt; 10     siz[k]=siz[rt]; 11     siz[rt]=siz[lc[rt]]+siz[rc[rt]]+1; 12     rt=k; 13 }   14 void l_rotate(int &rt){ 15     int k=rc[rt]; 16     rc[rt]=lc[k]; 17     lc[k]=rt; 18     siz[k]=siz[rt]; 19     siz[rt]=siz[lc[rt]]+siz[rc[rt]]+1; 20     rt=k; 21 } 22 void MAINTAIN(int &rt,bool flag){ 23     if(flag==false){ 24         if(siz[lc[lc[rt]]]>siz[rc[rt]]) r_rotate(rt); 25         else if(siz[rc[lc[rt]]]>siz[rc[rt]]){ 26             l_rotate(lc[rt]); 27             r_rotate(rt); 28         } 29         else return; 30     } 31     else{ 32         if(siz[rc[rc[rt]]]>siz[lc[rt]]) l_rotate(rt); 33         else if(siz[lc[rc[rt]]]>siz[lc[rt]]){ 34             r_rotate(rc[rt]); 35             l_rotate(rt); 36         } 37         else return; 38     } 39     MAINTAIN(lc[rt],0); MAINTAIN(rc[rt],1); 40     MAINTAIN(rt,1); MAINTAIN(rt,0); 41 } 42 void insert(int &rt,int v){ 43     if(rt==0){ 44         rt=++tot;  45         key[rt]=v; 46         lc[rt]=rc[rt]=0; siz[rt]=1; 47         return ; 48     } 49     siz[rt]++; 50     if(v<=key[rt]) insert(lc[rt],v); 51     else insert(rc[rt],v); 52     MAINTAIN(rt,v>key[rt]); 53 } 54 int Delete(int &rt,int v){ 55     int ans; 56     siz[rt]--; 57     if(v==key[rt]||(v
        
         key[rt]&&rc[rt]==0)){ 58         ans=key[rt]; 59         if(lc[rt]==0||rc[rt]==0) rt=lc[rt]+rc[rt]; 60         else key[rt]=Delete(lc[rt],key[rt]+1); 61         return ans; 62     } 63     if(v
         
          key[rt]) return find(rc[rt],v); 72 } 73 int rank(int &rt,int v){ 74     if(rt==0) return 1; 75     if(v<=key[rt]) return rank(lc[rt],v); 76     else return siz[lc[rt]]+1+rank(rc[rt],v); 77 } 78 int select(int &rt,int k){ 79     if(k==siz[lc[rt]]+1) return key[rt]; 80     if(k<=siz[lc[rt]]) return select(lc[rt],k); 81     else return select(rc[rt],k-1-siz[lc[rt]]); 82 } 83 int pred(int &rt,int v){ 84     if(rt==0) return v; 85     if(v<=key[rt]) return pred(lc[rt],v); 86     else{ 87         int ans=pred(rc[rt],v); 88         if(ans==v) return key[rt]; 89         return ans; 90     } 91 } 92 int succ(int &rt,int v){ 93     if(rt==0) return v; 94     if(v>=key[rt]) return succ(rc[rt],v); 95     else{ 96         int ans=succ(lc[rt],v); 97         if(ans==v) return key[rt]; 98         return ans; 99     }100 }101 void inorder(int rt){102     if(rt!=0){103         inorder(lc[rt]);104         cout<
          
           <<" ";105         inorder(rc[rt]);106     }107 }108 int main(){    109     siz[0]=root=tot=0;110     scanf("%d",&N);111     for(int i=1,kin,num;i<=N;i++){112         scanf("%d%d",&kin,&num);113         if(kin==1) insert(root,num);114         else if(kin==2) Delete(root,num);115         else if(kin==3) printf("%d\n",rank(root,num));116         else if(kin==4) printf("%d\n",select(root,num));117         else if(kin==5) printf("%d\n",pred(root,num));118         else if(kin==6) printf("%d\n",succ(root,num));119     }120     return 0;121 }

　　Splay版的：

1 #include
       
          2 #include
        
           3 #include
         
            4 #include
          
             5 #include
           
              6 #include
            
              7 #include
             
               8 using namespace std; 9 const int maxn=200000; 10 int key[maxn],lc[maxn],rc[maxn],fa[maxn],siz[maxn]; 11 int tot,root; 12 int T; 13 void update(int x){ 14 siz[x]=siz[lc[x]]+1+siz[rc[x]]; 15 } 16 void r_rotate(int x){ 17 int y=fa[x]; 18 lc[y]=rc[x]; 19 if(rc[x]!=0) fa[rc[x]]=y; 20 fa[x]=fa[y]; 21 if(y==lc[fa[y]]) lc[fa[y]]=x; 22 else rc[fa[y]]=x; 23 fa[y]=x; rc[x]=y; 24 update(x); update(y); 25 } 26 void l_rotate(int x){ 27 int y=fa[x]; 28 rc[y]=lc[x]; 29 if(lc[x]!=0) fa[lc[x]]=y; 30 fa[x]=fa[y]; 31 if(y==lc[fa[y]]) lc[fa[y]]=x; 32 else rc[fa[y]]=x; 33 fa[y]=x; lc[x]=y; 34 update(x); update(y); 35 } 36 void splay(int x,int s){ 37 int p; 38 while(fa[x]!=s){ 39 p=fa[x]; 40 if(fa[p]==s){ 41 if(x==lc[p]) r_rotate(x); 42 else l_rotate(x); 43 break; 44 } 45 if(x==lc[p]){ 46 if(p==lc[fa[p]]) r_rotate(p),r_rotate(x); 47 else r_rotate(x),l_rotate(x); 48 } 49 else{ 50 if(p==rc[fa[p]]) l_rotate(p),l_rotate(x); 51 else l_rotate(x),r_rotate(x); 52 } 53 } 54 if(s==0) root=x; 55 update(x); 56 } 57 int find(int v){ //查找在这棵树中键值为v的节点 58 int x=root; 59 while(x!=0){ 60 if(v
              
               key[x]) x=rc[x]; 62 else if(v==key[x]){ 63 splay(x,0); 64 return x; 65 } 66 } 67 return -1; 68 } 69 void New_node(int &x,int fath,int v){ //建立新节点 70 x=++tot; 71 lc[x]=rc[x]=0; siz[x]=1; 72 fa[x]=fath; 73 key[x]=v; 74 } 75 void insert(int v){ //插入新节点 76 if(root==0){ 77 New_node(rc[0],0,v); 78 root=tot; 79 return ; 80 } 81 int p,x=root; 82 while(x!=0){ 83 p=x; 84 if(v<=key[x]) siz[x]++,x=lc[x]; 85 else siz[x]++,x=rc[x]; 86 } 87 if(v<=key[p]) New_node(lc[p],p,v); 88 else New_node(rc[p],p,v); 89 splay(tot,0); 90 } 91 int getmax(int x){ //找到以x为根的最大值 92 if(rc[x]!=0) return getmax(rc[x]); 93 return x; 94 } 95 int getmin(int x){ //找到以x为根的最小值 96 if(lc[x]!=0) return getmin(lc[x]); 97 return x; 98 } 99 int getpre(int x){ //找到节点x的前驱 100 splay(x,0);101 return getmax(lc[x]);102 }103 int getne(int x){ //找到节点x的后继104 splay(x,0);105 return getmin(rc[x]);106 }107 void Delete(int v){108 int x=find(v);109 int pp=getmax(lc[x]);110 int nn=getmin(rc[x]);111 if(lc[x]==0||rc[x]==0){112 if(lc[x]==0&&rc[x]==0){113 root=0; rc[0]=0; 114 return ;115 }116 if(lc[x]==0){117 rc[0]=rc[x]; fa[rc[x]]=0; root=rc[x]; rc[x]=0;118 siz[x]=1;119 return ;120 }121 else{122 rc[0]=lc[x]; fa[lc[x]]=0; root=lc[x]; lc[x]=0;123 siz[x]=1;124 return ;125 }126 }127 splay(pp,0);128 splay(nn,root);129 fa[lc[nn]]=0; siz[lc[nn]]=1; lc[nn]=0;130 update(nn); update(pp);131 } 132 int rank(int rt,int v){ //返回键值为v的节点的排名 133 if(rt==0) return 1;134 if(v<=key[rt]) return rank(lc[rt],v);135 else return siz[lc[rt]]+1+rank(rc[rt],v); 136 }137 int findkth(int x,int k){ //在以x为根的树中找第 k大 138 if(siz[lc[x]]+1==k) return key[x];139 if(siz[lc[x]]+1>k) return findkth(lc[x],k);140 return findkth(rc[x],k-siz[lc[x]]-1);141 }142 143 int pred(int rt,int v){ //返回比 v小的最大的数 144 if(rt==0) return v;145 if(v<=key[rt]) return pred(lc[rt],v);146 else{147 int ans=pred(rc[rt],v);148 if(ans==v) return key[rt]; 149 return ans;150 }151 }152 int succ(int rt,int v){ //返回比 v大的最小的数 153 if(rt==0) return v;154 if(v>=key[rt]) return succ(rc[rt],v);155 else{156 int ans=succ(lc[rt],v); 157 if(ans==v) return key[rt];158 return ans;159 }160 }161 int main(){162 freopen("phs.in","r",stdin);163 freopen("phs.out","w",stdout);164 scanf("%d",&T);165 while (T--){166 int kin,num;167 scanf("%d%d",&kin,&num);168 if(kin==1) 169 insert(num);//插入 170 else if(kin==2) 171 Delete(num);//删除(若有多个相同的数，只删除一个)172 else if(kin==3) 173 printf("%d\n",rank(root,num));//查询num数的排名(若有多个相同的数，因输出最小的排名)174 else if (kin==4) 175 printf("%d\n",findkth(root,num));//查询排名为x的数 176 else if (kin==5) 177 printf("%d\n",pred(root,num)); 178 else if (kin==6) 179 printf("%d\n",succ(root,num));180 }181 return 0;182 }

　　vector版的：

1 #include
       
         2 #include
        
          3 #include
         
           4 using namespace std; 5 const int INF=10000000; 6 int n; 7 vector
          
            tree; 8 int find(int x){ 9     return lower_bound(tree.begin(),tree.end(),x)-tree.begin()+1;10 }11 int main(){12     scanf("%d",&n);13     tree.reserve(200000);14     for(int i=1,kin,x;i<=n;i++){15         scanf("%d%d",&kin,&x);16         if(kin==1) tree.insert(upper_bound(tree.begin(),tree.end(),x),x);17         else if(kin==2) tree.erase(lower_bound(tree.begin(),tree.end(),x));18         else if(kin==3) printf("%d\n",find(x));19         else if(kin==4) printf("%d\n",tree[x-1]);20         else if(kin==5) printf("%d\n",*--lower_bound(tree.begin(),tree.end(),x));21         else if(kin==6) printf("%d\n",*upper_bound(tree.begin(),tree.end(),x));22     }23     return 0;24 }