3224: Tyvj 1728 普通平衡树

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 20328  Solved: 8979

[][][]

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

 

[ ][ ][ ]

刷点模板题。。发现自己treap忘光了。。

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

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

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #define rep(i,l,r) for (int i=l; i<=r; i++) 6 using namespace std; 7  8 const int N=100100,inf=1000000000; 9 int n,rt,nd,ans,op,x,ls[N],rs[N],sz[N],h[N],v[N],w[N];10 11 void rrot(int &x){12     int y=ls[x]; ls[x]=rs[y]; rs[y]=x;13     sz[y]=sz[x]; sz[x]=sz[ls[x]]+sz[rs[x]]+w[x]; x=y;14 }15 16 void lrot(int &x){17     int y=rs[x]; rs[x]=ls[y]; ls[y]=x;18     sz[y]=sz[x]; sz[x]=sz[ls[x]]+sz[rs[x]]+w[x]; x=y;19 }20 21 void ins(int &x,int k){22     if (!x){23         x=++nd; v[x]=k; h[x]=rand(); sz[x]=w[x]=1; return;24     }25     sz[x]++;26     if (v[x]==k) { w[x]++; return; }27     if (k
         
          1) { w[x]--; sz[x]--; return; }34         if (!ls[x] || !rs[x]) { x=ls[x]+rs[x]; return; }35         if (h[ls[x]]
          
           =k) return v[x];51 if (sz[ls[x]]>=k) return find(ls[x],k);52 else return find(rs[x],k-sz[ls[x]]-w[x]);53 }54 55 void pre(int x,int k){56 if (!x) return;57 if (v[x]
           
            k) ans=min(ans,v[x]),nxt(ls[x],k); else nxt(rs[x],k);63 }64 65 int main(){66 freopen("bzoj3224.in","r",stdin);67 freopen("bzoj3224.out","w",stdout);68 for (scanf("%d",&n); n--; ){69 scanf("%d%d",&op,&x);70 if (op==1) ins(rt,x);71 if (op==2) del(rt,x);72 if (op==3) printf("%d\n",get(rt,x));73 if (op==4) printf("%d\n",find(rt,x));74 if (op==5) ans=0,pre(rt,x),printf("%d\n",ans);75 if (op==6) ans=inf,nxt(rt,x),printf("%d\n",ans);76 }77 return 0;78 }
           
          
         
        
       
      
     

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

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

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