[BZOJ3224]普通平衡树(旋转treap,STL-vector)

3224: Tyvj 1728 普通平衡树

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 20328  Solved: 8979
[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忘光了。。

没什么好说的，题目里的排名是指从小到大，其余没有什么坑点，那些作为函数哪些作为过程要想清楚。

比无旋treap快，所以说到现在都没有遇上必须用无旋treap的题，除了WC的那道可持久化treap。

 #include<cstdio>
 #include<cstdlib>
 #include<cstring>
 #include<algorithm>
 #define rep(i,l,r) for (int i=l; i<=r; i++)
 using namespace std;

 const int N=,inf=;
 int n,rt,nd,ans,op,x,ls[N],rs[N],sz[N],h[N],v[N],w[N];

 void rrot(int &x){
     int y=ls[x]; ls[x]=rs[y]; rs[y]=x;
     sz[y]=sz[x]; sz[x]=sz[ls[x]]+sz[rs[x]]+w[x]; x=y;
 }

 void lrot(int &x){
     int y=rs[x]; rs[x]=ls[y]; ls[y]=x;
     sz[y]=sz[x]; sz[x]=sz[ls[x]]+sz[rs[x]]+w[x]; x=y;
 }

 void ins(int &x,int k){
     if (!x){
         x=++nd; v[x]=k; h[x]=rand(); sz[x]=w[x]=; return;
     }
     sz[x]++;
     if (v[x]==k) { w[x]++; return; }
     if (k<v[x]){ ins(ls[x],k); if (h[ls[x]]<h[x]) rrot(x);}
      else { ins(rs[x],k); if (h[rs[x]]<h[x]) lrot(x); }
 }

 void del(int &x,int k){
     if (v[x]==k){
         if (w[x]>) { w[x]--; sz[x]--; return; }
         if (!ls[x] || !rs[x]) { x=ls[x]+rs[x]; return; }
         if (h[ls[x]]<h[rs[x]]) rrot(x),del(x,k); else lrot(x),del(x,k);
         return;
     }
     sz[x]--;
     if (k<v[x]) del(ls[x],k); else del(rs[x],k);
 }

 int get(int x,int k){
     if (!x) return ;
     if (v[x]==k) return sz[ls[x]]+;
     else if (k<v[x]) return get(ls[x],k); else return sz[ls[x]]+w[x]+get(rs[x],k);
 }

 int find(int x,int k){
     if (!x) return ;
     if (sz[ls[x]]+<=k && sz[ls[x]]+w[x]>=k) return v[x];
     if (sz[ls[x]]>=k) return find(ls[x],k);
         else return find(rs[x],k-sz[ls[x]]-w[x]);
 }

 void pre(int x,int k){
     if (!x) return;
     if (v[x]<k) ans=max(ans,v[x]),pre(rs[x],k); else pre(ls[x],k);
 }

 void nxt(int x,int k){
     if (!x) return;
     if (v[x]>k) ans=min(ans,v[x]),nxt(ls[x],k); else nxt(rs[x],k);
 }

 int main(){
     freopen("bzoj3224.in","r",stdin);
     freopen("bzoj3224.out","w",stdout);
     for (scanf("%d",&n); n--; ){
         scanf("%d%d",&op,&x);
         if (op==) ins(rt,x);
         if (op==) del(rt,x);
         if (op==) printf("%d\n",get(rt,x));
         if (op==) printf("%d\n",find(rt,x));
         if (op==) ans=,pre(rt,x),printf("%d\n",ans);
         if (op==) ans=inf,nxt(rt,x),printf("%d\n",ans);
     }
     return ;
 }

懒得写这么多怎么办，上STL-vector，所有操作都能在库函数里找到。

据说单次操作理论复杂度是线性的，实际上可以看作是根号的，但这里也只慢了一倍而已。

 #include<cstdio>
 #include<vector>
 #include<algorithm>
 #define rep(i,l,r) for (int i=l; i<=r; i++)
 using namespace std;

 const int inf=;
 int n,op,x;
 vector<int>a;

 int main(){
     scanf("%d",&n); a.reserve();
     rep(i,,n){
         scanf("%d%d",&op,&x);
         if (op==) a.insert(upper_bound(a.begin(),a.end(),x),x);
         if (op==) a.erase(lower_bound(a.begin(),a.end(),x));
         if (op==) printf("%d\n",int(lower_bound(a.begin(),a.end(),x)-a.begin()+));
         if (op==) printf("%d\n",a[x-]);
         if (op==) printf("%d\n",*(--lower_bound(a.begin(),a.end(),x)));
         if (op==) printf("%d\n",*upper_bound(a.begin(),a.end(),x));
     }
     return ;
 }