zcmu-1954

1954: #104. 普通平衡树

Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 37 Solved: 18
[Submit][Status][Web Board]
Description

这是一道模板题。

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

插入 x 数；
删除 x数（若有多个相同的数，因只删除一个）；
查询 x 数的排名（若有多个相同的数，因输出最小的排名）；
查询排名为 x 的数；
求 x 的前趋（前趋定义为小于 x ，且最大的数）；
求 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≤105,−107≤x≤107

思路：套模板题 自己对树的理解不透彻 这题纯粹的套他人模板。理解还是要的，毕竟模板不是万能的。

ac代码：

#include<bits/stdc++.h> using namespace std;struct treap {int l,r,sz,num,rd,val; }p[2000000];int m,size,root,ans;void update(int k) {p[k].sz=p[p[k].l].sz+p[p[k].r].sz+p[k].num; }void left_rotate(int &k) {int y=p[k].r;p[k].r=p[y].l;p[y].l=k;p[y].sz=p[k].sz;update(k);k=y; }void right_rotate(int &k) {int y=p[k].l;p[k].l=p[y].r;p[y].r=k;p[y].sz=p[k].sz;update(k);k=y; }void insert(int &k,int x) {if(k==0){++size;k=size;p[k].sz=p[k].num=1;p[k].val=x;p[k].rd=rand();return ;}++p[k].sz;if(p[k].val==x) p[k].num++;else if(x>p[k].val){insert(p[k].r,x);if(p[p[k].r].rd<p[k].rd) left_rotate(k);}else{insert(p[k].l,x);if(p[p[k].l].rd<p[k].rd) right_rotate(k);} }void del(int &k,int x) {if(k==0) return ;if(p[k].val==x){if(p[k].num>1){p[k].num--;p[k].sz--;return ;}if(p[k].r*p[k].l==0)k=p[k].l+p[k].r;else if(p[p[k].l].rd<p[p[k].r].rd) right_rotate(k),del(k,x);else left_rotate(k),del(k,x);}else if(x>p[k].val) --p[k].sz,del(p[k].r,x);else --p[k].sz,del(p[k].l,x); }int find_rank(int k,int x) {if(k==0) return 0;if(p[k].val==x) return p[p[k].l].sz+1;elseif(x>p[k].val) return p[p[k].l].sz+p[k].num+find_rank(p[k].r,x);else return find_rank(p[k].l,x); }int rerank(int k,int x) {if(k==0) return 0;if(x<=p[p[k].l].sz) return rerank(p[k].l,x);else if(x>p[p[k].l].sz+p[k].num)return rerank(p[k].r,x-p[p[k].l].sz-p[k].num);else return p[k].val; }void succ(int k,int x) {if(k==0) return ;if(p[k].val>x){ans=k;succ(p[k].l,x);}else succ(p[k].r,x); }void pred(int k,int x) {if(k==0)return ;if(p[k].val<x){ans=k;pred(p[k].r,x);}else pred(p[k].l,x); } int main() {cin>>m;int t1,t2;for(int i=1;i<=m;i++){cin>>t1>>t2;ans=0;if(t1==1)insert(root,t2);if(t1==2)del(root,t2);if(t1==3)cout<<find_rank(root,t2)<<endl;if(t1==4)cout<<rerank(root,t2)<<endl;if(t1==5){pred(root,t2);cout<<p[ans].val<<endl;}if(t1==6){succ(root,t2);cout<<p[ans].val<<endl;}}return 0; }

总结

以上是生活随笔为你收集整理的zcmu-1954的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。