首页 > 代码库 > 【bzoj】3224: Tyvj 1728 普通平衡树

【bzoj】3224: Tyvj 1728 普通平衡树

2024-09-01 08:41:03   220人阅读

3224: Tyvj 1728 普通平衡树

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 10097  Solved: 4302
[Submit][Status][Discuss]

Description

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
1. 插入x数
2. 删除x数(若有多个相同的数，因只删除一个)
3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)

Input

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

Output

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

Sample Input

10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598

Sample Output

106465
84185
492737

HINT

 

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

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

数据如下http://pan.baidu.com/s/1jHMJwO2
一万年没写数据结构了，来发treap模板练练手/
  1 #include<iostream>  2 #include<cstdio>  3 #include<algorithm>  4 #include<vector>  5 #include<cstdlib>  6 #include<cmath>  7 #include<cstring>  8 using namespace std;  9 #define maxn 110010 10 #define llg  int 11 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); 12 int n,m,ans; 13  14 inline int getint() 15 { 16        int w=0,q=0; 17        char c=getchar(); 18        while((c<‘0‘ || c>‘9‘) && c!=‘-‘) c=getchar(); 19        if (c==‘-‘)  q=1, c=getchar(); 20        while (c>=‘0‘ && c<=‘9‘) w=w*10+c-‘0‘, c=getchar(); 21        return q ? -w : w; 22 } 23  24 struct MYTREAP 25 { 26     int root,size; 27     struct  28     { 29         int l,r,rnd,val,w,size; 30     }po[maxn]; 31      32     void init(){ memset(po,0,sizeof(po)); root=size=0;} 33      34     void update(llg now) {po[now].size=po[po[now].l].size+po[po[now].r].size+po[now].w;} 35          36     void right_(llg &now) {llg t=po[now].l; po[now].l=po[t].r; po[t].r=now; po[t].size=po[now].size; update(now); now=t;} 37     void left_(llg &now)  {llg t=po[now].r; po[now].r=po[t].l; po[t].l=now; po[t].size=po[now].size; update(now); now=t;} 38  39     void in(llg val) 40     { 41         insert(root,val); 42     } 43  44     void insert(llg &now,llg val) 45     { 46         if (now==0) 47         { 48             now=++size; 49             po[now].size=po[now].w=1; po[now].val=val; po[now].rnd=rand(); 50             return ; 51         } 52         po[now].size++; 53         if (po[now].val==val) 54         { 55             po[now].w++; 56         } 57         else 58             if (po[now].val<val) 59             { 60                 insert(po[now].r,val); 61                 if (po[po[now].r].rnd<po[now].rnd) left_(now); 62             } 63             else 64             { 65                 insert(po[now].l,val); 66                 if (po[po[now].l].rnd<po[now].rnd) right_(now); 67             } 68     } 69      70     void del(llg &now,llg val) 71     { 72         if (now==0) return ; 73         if (po[now].val==val) 74         { 75             if (po[now].w>1) 76             { 77                 po[now].w--; po[now].size--; 78                 return ; 79             } 80             if (po[now].l*po[now].r==0) now=po[now].l+po[now].r; 81             else 82             { 83                 if (po[po[now].l].rnd<po[po[now].r].rnd) right_(now); else left_(now); 84                 del(now,val); 85             } 86         } 87         else 88         { 89             po[now].size--; 90             if (val>po[now].val) del(po[now].r,val); 91             else del(po[now].l,val); 92         } 93     } 94  95     int ask_rank(llg now,llg val) 96     { 97         if (now==0) return 0; 98         if (po[now].val==val) return po[po[now].l].size+1; 99         else100             if (val>po[now].val) return po[po[now].l].size+po[now].w+ask_rank(po[now].r,val);101             else return ask_rank(po[now].l,val);102     }103 104     int ask_num(llg now,int val)105     {106         if (now==0) return 0;107         if (val<=po[po[now].l].size) 108             return ask_num(po[now].l,val);109         else if (val>po[po[now].l].size+po[now].w) 110             return ask_num(po[now].r,val-po[po[now].l].size-po[now].w);111         else 112             return po[now].val; 113     }114 115     void pre(llg now,llg val)116     {117         if (now==0) return ;118         if (po[now].val<val)119         {120             ans=now; 121             pre(po[now].r,val);122         }123         else pre(po[now].l,val);124     }125 126     void nex(llg now,llg val)127     {128         if (now==0) return ;129         if (po[now].val>val)130         {131             ans=now;132             nex(po[now].l,val);133         }134         else nex(po[now].r,val);135     }136 137 }tree;138 139 int main()140 {141     yyj("3224");142     srand(1346);143     tree.init();144     cin>>n;145     llg ty,x;146     for (llg i=1;i<=n;i++)147     {148         ty=getint(),x=getint();149         switch(ty)150         {151             case 1:tree.in(x);break;152             case 2:tree.del(tree.root,x);break;153             case 3:printf("%d\n",tree.ask_rank(tree.root,x));break;154             case 4:printf("%d\n",tree.ask_num(tree.root,x));break;155             case 5:ans=0;tree.pre(tree.root,x);printf("%d\n",tree.po[ans].val);break;156             case 6:ans=0;tree.nex(tree.root,x);printf("%d\n",tree.po[ans].val);break;157         }158     }159     return 0;160 }

 

 
 

【bzoj】3224: Tyvj 1728 普通平衡树


联系
我们