3224: Tyvj 1728 普通平衡樹

Time Limit: 1 Sec??

Memory Limit: 256 MB

題目連接

http://www.lydsy.com/JudgeOnline/problem.php?id=3224

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]

題意

?

題解：

treap，當然這個版是抄的：http://www.cnblogs.com/iwtwiioi/p/3869598.html

代碼：

//qscqesze #include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <bitset> #include <vector> #include <sstream> #include <queue> #include <typeinfo> #include <fstream> #include <map> #include <stack> typedef long long ll; using namespace std; //freopen("D.in","r",stdin); //freopen("D.out","w",stdout); #define sspeed ios_base::sync_with_stdio(0);cin.tie(0) #define maxn 1200051 #define mod 10007 #define eps 1e-9 int Num; //const int inf=0x7fffffff; //нчоч╢С const int inf=~0u>>1; inline ll read() {ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } //************************************************************************************** struct Treap {struct node{node* ch[2];int key,size,wei,cnt;node(int _key,node* f){ch[0]=ch[1]=f;key=_key;size=cnt=1;wei=rand();}void pushup(){size=ch[0]->size+ch[1]->size+cnt;}}*null,*root;Treap(){null = new node(0,0);null->size=null->cnt=0;null->wei=inf;root = null;}void rot(node* &rt,bool d){node* c = rt->ch[!d];rt->ch[!d]=c->ch[d];c->ch[d]=rt;rt->pushup();c->pushup();rt=c;}void insert(const int &key,node* &rt){if(rt==null){rt=new node(key,null);return;}if(key==rt->key){rt->cnt++;rt->size++;return;}bool d=key>rt->key;insert(key,rt->ch[d]);if(rt->wei>rt->ch[d]->wei)rot(rt,!d);rt->pushup();}void remove(const int &key,node* &rt){if(rt==null)return;bool d=key>rt->key;if(key==rt->key){if(rt->cnt>1){rt->cnt--;rt->size--;return;}d=rt->ch[0]->wei>rt->ch[1]->wei;if(rt->ch[d]==null){delete rt;rt=null;return;}rot(rt,!d);remove(key,rt->ch[!d]);}elseremove(key,rt->ch[d]);rt->pushup();}node* select(int k,node* rt){int s=rt->ch[0]->size+rt->cnt;if(k>=rt->ch[0]->size+1 && k<=s)return rt;if(s>k)return select(k,rt->ch[0]);else return select(k-s,rt->ch[1]);}int rank(const int &key,node* rt){if(rt==null)return 0;int s=rt->ch[0]->size+rt->cnt;if(key==rt->key)return rt->ch[0]->size+1;if(key<rt->key)return rank(key,rt->ch[0]);else return s+rank(key,rt->ch[1]);}int suc(const int &k){node* t = root;int ret=0;while(t!=null){if(t->key>k){ret=t->key;t=t->ch[0];}elset=t->ch[1];}return ret;}int pre(const int &k){node* t = root;int ret=0;while(t!=null){if(t->key<k){ret=t->key;t=t->ch[1];}elset=t->ch[0];}return ret;} };int main() {int n,a,b;Treap tree;n=read();while(n--){a=read(),b=read();if(a==1)tree.insert(b,tree.root);if(a==2)tree.remove(b,tree.root);if(a==3)printf("%d\n",tree.rank(b,tree.root));if(a==4)printf("%d\n",tree.select(b,tree.root)->key);if(a==5)printf("%d\n",tree.pre(b));if(a==6)printf("%d\n",tree.suc(b));}return 0; }

?

總結

以上是生活随笔為你收集整理的BZOJ 3224: Tyvj 1728 普通平衡树 treap的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。