bzoj3224 Tyvj 1728 普通平衡树(名次树+处理相同)

时间:2023-01-28 20:12:24

3224: Tyvj 1728 普通平衡树

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 5354  Solved: 2196
[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.每个数的数据范围:[-1e7,1e7]

【思路】

Rank tree

Treap实现名次树。需要多维护s,w域分别表示节点数目与相同键值的数目,相应修改maintain,remove和rank操作。

需要注意的是不能单单在insert的时候安排相同结点放在右子,因为有可能结点通过旋转转上来,这就违反了我们的初衷。

【代码】

 #include<cstdio>
#include<ctime>
#include<cstring>
#include<cstdlib>
#include<iostream>
#define FOR(a,b,c) for(int a=(b);a<=(c);a++)
using namespace std; struct Node{
Node* ch[];
int v,r,s,w;
Node(int x):v(x) { ch[]=ch[]=NULL; s=w=; r=rand(); }
void maintain() {
s=w; //change
if(ch[]!=NULL) s+=ch[]->s;
if(ch[]!=NULL) s+=ch[]->s;
}
int cmp(int x) const {
if(x==v) return -; return x<v?:;
}
};
void rotate(Node* &o,int d) {
Node* k=o->ch[d^]; o->ch[d^]=k->ch[d]; k->ch[d]=o;
o->maintain(); k->maintain(); o=k;
}
//不能只是把大于等于x的放在右子树 有可能旋上来
void insert(Node* &o,int x) {
if(o==NULL) o=new Node(x);
else {
int d=o->cmp(x);
if(d==-) { o->w++; o->maintain(); return; } //相同键值的个数
insert(o->ch[d],x);
if(o->ch[d]->r > o->r) rotate(o,d^);
}
o->maintain();
}
void remove(Node* &o,int x){
if(o==NULL) return ;
int d=o->cmp(x);
if(d==-) {
Node* u=o;
if(o->w>) { o->w--; o->maintain(); return ; } //change2
if(o->ch[]!=NULL && o->ch[]!=NULL) {
int d2=o->ch[]->r > o->ch[]->r? :;
rotate(o,d2); remove(o->ch[d2],x);
}
else {
if(o->ch[]!=NULL) o=o->ch[]; else o=o->ch[];
delete u;
}
}
else remove(o->ch[d],x);
if(o!=NULL) o->maintain();
}
int kth(Node* o,int k) {
if(o==NULL || k<= || k>o->s) return ;
int s=o->ch[]==NULL? :o->ch[]->s,w=o->w;
if(s+<=k && k<=s+w) return o->v;
else if(k<=s) return kth(o->ch[],k);
else return kth(o->ch[],k-s-w);
}
int rank(Node* o,int x) {
if(o==NULL) return ;
int d=o->cmp(x),s=o->ch[]==NULL?:o->ch[]->s;
int f= d==? s+o->w:;
if(d==-) return s+;
else return rank(o->ch[d],x)+f;
}
void query1(Node* o,int x,int& ans) {
if(o==NULL) return ;
if(o->v<x) { ans=o->v; query1(o->ch[],x,ans); }
else query1(o->ch[],x,ans);
}
void query2(Node* o,int x,int& ans) {
if(o==NULL) return ;
if(o->v>x) { ans=o->v; query2(o->ch[],x,ans); }
else query2(o->ch[],x,ans);
}
int n,opt,x,ans;
Node* root=NULL; int main() {
//srand(time(0)); //bzoj上不要用 否则RE
scanf("%d",&n);
FOR(i,,n) {
scanf("%d%d",&opt,&x);
switch(opt) {
case : insert(root,x); break;
case : remove(root,x); break;
case : printf("%d\n",rank(root,x)); break;
case : printf("%d\n",kth(root,x)); break;
case : ans=; query1(root,x,ans); printf("%d\n",ans); break;
case : ans=; query2(root,x,ans); printf("%d\n",ans); break;
}
}
return ;
}