【bzoj 3224】Tyvj 1728 普通平衡树

Tyvj 1728 普通平衡树

Time Limit: 10 Sec Memory Limit: 128 MB Submit: 11767 Solved: 5021 [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.每个数的数据范围：[-2e9,2e9] Source

平衡树

[Submit][Status][Discuss] 复习下treap

#include<bits/stdc++.h> using namespace std; const int maxn = 100065; int l[maxn],r[maxn],v[maxn],rnd[maxn],w[maxn],sz[maxn]; int n,cnt,root,ans; void pushUp(int rt) { sz[rt]=sz[l[rt]]+sz[r[rt]]+w[rt]; } void rturn(int &k) { int t=l[k];l[k]=r[t];r[t]=k; sz[t]=sz[k];pushUp(k);k=t; } void lturn(int &k) { int t=r[k];r[k]=l[t];l[t]=k; sz[t]=sz[k];pushUp(k);k=t; } void ins(int &k,int x) { if(k==0){ k=++cnt;sz[k]=w[k]=1;v[k]=x;rnd[k]=rand();return; } sz[k]++; if(v[k]==x)w[k]++; else if(x>v[k]){ ins(r[k],x); if(rnd[r[k]] < rnd[k])lturn(k); } else{ ins(l[k],x); if(rnd[l[x]] < rnd[k])rturn(k); } } void del(int &k,int x){ if(k==0)return; if(v[k]==x){ if(w[k]>1){ w[k]--;sz[k]--;return; } if(l[k]*r[k]==0)k=l[k]+r[k]; else if(rnd[l[k]] < rnd[r[k]]){ rturn(k);del(k,x); } else lturn(k),del(k,x); } else if(x>v[k]) sz[k]--,del(r[k],x); else sz[k]--,del(l[k],x); } int rank(int k,int x) { if(!k)return k; if(v[k]==x)return sz[l[k]]+1; else if(x>v[k]) return rank(r[k],x)+sz[l[k]]+w[k]; else return rank(l[k],x); } int kth(int k,int x) { if(!k)return k; if(x<=sz[l[k]]) return kth(l[k],x); else if(x>sz[l[k]]+w[k]) return kth(r[k],x-sz[l[k]]-w[k]); else return v[k]; } void pro(int k,int x) { if(!k)return; if(v[k]<x){ ans=k;pro(r[k],x); } else pro(l[k],x); } void afs(int k,int x) { if(!k)return; if(v[k]>x){ ans=k;afs(l[k],x); } else afs(r[k],x); } int main() { scanf("%d",&n); int opt,x; for(int i=1;i<=n;i++){ scanf("%d %d",&opt,&x); switch(opt) { case 1:ins(root,x);break; case 2:del(root,x);break; case 3:printf("%d\n",rank(root,x));break; case 4:printf("%d\n",kth(root,x));break; case 5:ans=0;pro(root,x);printf("%d\n",v[ans]);break; case 6:ans=0;afs(root,x);printf("%d\n",v[ans]);break; } } return 0; }