[Tyvj 1728]普通平衡树

发表于 | 分类于

题目

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

  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

OUTPUT

106465
84185
492737

解题报告

一道裸的平衡树板子题，也是我的Treap首题，留念

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
using namespace std;
inline int read(){
	int sum(0),f(1);
	char ch(getchar());
	while(ch<'0'||ch>'9'){
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		sum=sum*10+ch-'0';
		ch=getchar();
	}
	return sum*f;
}
struct node{
	int size,key,v;
	node *ch[2];
	node():size(1),key(rand()),v(0){
		ch[0]=ch[1]=NULL;
	}
	node(int x):size(1),key(rand()),v(x){
		ch[0]=ch[1]=NULL;
	}
}*root;
inline int get_size(node *x){
	if(x==NULL)
		return 0;
	return x->size;
}
inline void pushup(node *rt){
	rt->size=get_size(rt->ch[0])+get_size(rt->ch[1])+1;
}
inline void ro(node *&rt,int d){
	node *tmp(rt->ch[d^1]);
	rt->ch[d^1]=tmp->ch[d];
	pushup(rt);
	tmp->ch[d]=rt;
	pushup(tmp);
	rt=tmp;
}
inline void insert(node *&rt,int x){
	if(!rt){
		rt=new node(x);
		return;
	}
	int d(rt->v>x);
	insert(rt->ch[d^1],x);
	pushup(rt);
	if(rt->ch[d^1]->key>rt->key)
		ro(rt,d);
}
inline void del(node *&rt,int x){
	if(rt->v==x){
		if(rt->ch[0]!=NULL&&rt->ch[1]!=NULL){
			int d(rt->ch[0]->key>rt->ch[1]->key);
			ro(rt,d);
			del(rt->ch[d],x);
		}
		else{
			node *tmp=NULL;
			if(rt->ch[0]!=NULL)
				tmp=rt->ch[0];
			else
				tmp=rt->ch[1];
			delete rt;
			rt=tmp;
		}
	}
	else{
		int d(rt->v>x);
		del(rt->ch[d^1],x);
	}
	if(rt!=NULL)
		pushup(rt);
}
inline int rk(int x){
	node *rt(root);
	int ret(0);
	while(rt){
		if(x>rt->v){
			ret+=get_size(rt->ch[0])+1;
			rt=rt->ch[1];
		}
		else
			rt=rt->ch[0];
	}
	return ret;
}
inline int kth(int k){
	node *rt(root);
	while(rt){
		if(get_size(rt->ch[0])+1==k)
			return rt->v;
		if(get_size(rt->ch[0])+1>k)
			rt=rt->ch[0];
		else{
			k-=get_size(rt->ch[0])+1;
			rt=rt->ch[1];
		}
	}
	return 0;
}
inline int gg(){
	freopen("phs.in","r",stdin);
	freopen("phs.out","w",stdout);
	srand(time(NULL));
	int n(read());
	while(n--){
		int op(read()),x(read());
		if(op==1){
			insert(root,x);
			continue;
		}
		if(op==2){
			del(root,x);
			continue;
		}
		if(op==3){
			printf("%d\n",rk(x)+1);
			continue;
		}
		if(op==4){
			printf("%d\n",kth(x));
			continue;
		}
		if(op==5){
			printf("%d\n",kth(rk(x)));
			continue;
		}
		if(op==6){
			printf("%d\n",kth(rk(x+1)+1));
			continue;
		}
	}
}
int k(gg());
int main(){;}

玄学板子，调的时间比打的时间还长= =
ps：参数类型一定要写对QWQ