스 트 레 칭 트 리 기초 (Splay)
30973 단어 play
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 3948 Solved: 1627 [ Submit ][ Status ][ Discuss ]
Description
데이터 구 조 를 작성 해 야 합 니 다.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]
아래 코드 는 템 플 릿 식 문제 풀이 이 며 상세 한 설명 이 있 습 니 다.
1 #include<cstdio>
2 #include<cstdlib>
3 #include<iostream>
4 #include<algorithm>
5 #include<cmath>
6 #include<cstring>
7 #include<queue>
8 using namespace std;
9 struct splay
10 {
11 int data,lc,rc,fa;
12 int size;// ，
13 }a[100005];
14
15 int q,root=0,tot=0;
16
17 void update(int x){// x size
18 a[x].size=a[a[x].lc].size+a[a[x].rc].size+1;// ： +1，
19 }
20
21 void r_rotate(int x){// x
22 /*
23 ：
24 ： x，y ，x y
25 ：x ，y ( )
26 ：
27 1. x ， y ( x) x ( x y)
28 2.x y ，
29 3. x y size
30 */
31 int y=a[x].fa;//y x
32 // 1：
33 a[y].lc=a[x].rc;//
34 if(a[x].rc!=0)// x :
35 a[a[x].rc].fa=y;// x y
36 // 2:
37 a[x].fa=a[y].fa;//
38 if (y==a[a[y].fa].lc)// y
39 a[a[y].fa].lc=x;
40 else// y
41 a[a[y].fa].rc=x;
42 // 3:
43 a[y].fa=x;
44 a[x].rc=y;// ： y x
45 update(y);// y size
46 update(x);// x size
47 }
48 void l_rotate(int x){//
49 int y=a[x].fa;
50 a[y].rc=a[x].lc;
51 if (a[x].lc!=0) a[a[x].lc].fa=y;
52 a[x].fa=a[y].fa;
53 if (y==a[a[y].fa].lc) a[a[y].fa].lc=x;
54 else a[a[y].fa].rc=x;
55 a[y].fa=x;
56 a[x].lc=y;
57 update(y);
58 update(x);
59 }
60 void splay(int x,int s){// x s
61 /**/
62 while (a[x].fa!=s){
63 if (x==a[a[x].fa].lc)// x
64 r_rotate(x);//
65 else// x
66 l_rotate(x);//
67 }
68 update(x);// x size
69 if (s==0)// x 0 ，x
70 root=x;
71 }
72
73 int Search(int w){// data
74 int p,x=root;
75 while(x){
76 p=x;
77 // ： x， data x data
78 // data x data
79 if (a[x].data>w)// data data，
80 x=a[x].lc;
81
82 else x=a[x].rc;//
83 }
84 return p;
85 }
86
87 void New_Node(int &x,int fa,int key){// x， 0，
88 // fa， key
89 x=++tot;// root=tot
90 a[x].lc=a[x].rc=0;
91 a[x].fa=fa;
92 a[x].data=key;
93 }
94 void Insert(int w)// data w ，
95 {
96 if (root==0)// ，
97 {
98 New_Node(root,0,w);
99 return;
100 }
101 //
102 int i=Search(w);//
103 if (w<a[i].data)// data ，
104 New_Node(a[i].lc,i,w);
105 //
106 else New_Node(a[i].rc,i,w);
107
108 splay(tot,0);// 0 ， （ ）
109 }
110 int Get(int w){// data w ， ： .data> .data> .data
111 int x=root;
112 int ans=tot+1;
113 while(x!=0){
114 if(a[x].data>w){
115 x=a[x].lc;
116 continue;
117 }
118 if(a[x].data<w){
119 x=a[x].rc;
120 continue;
121 }
122 if(a[x].data==w){
123 ans=x;
124 x=a[x].lc;
125 }
126 }
127 if (ans==tot+1) return -1;
128 return ans;
129 }
130
131 int Getmax(int x){// x data
132 while(a[x].rc!=0)
133 x=a[x].rc;
134 return x;
135 }
136
137 int Getmin(int x){// x data
138 while(a[x].lc!=0)
139 x=a[x].lc;
140 return x;
141 }
142
143 int Getpre(int x){
144 return Getmax(a[root].lc);
145 }
146
147 int Getne(int x){
148 return Getmin(a[root].rc);
149 }
150
151 void Delet(int w){// data w ，
152 /*
153 ：
154 1. 。
155 2. L ， ，L 。
156 3. R
157 4. ， L（ ） R（ ）。
158 R L 。
159 */
160 // 1：
161 int x=Get(w);
162 splay(x,0);//
163 // 2：
164 int pp=Getpre(x);
165 // 3：
166 int nn=Getne(x);
167
168 splay(pp,0);// x
169 splay(nn,root);// x
170 // 4:
171 int y=a[x].fa;
172 a[x].fa=0;
173 if (x==a[y].lc) a[y].lc=0;
174 else a[x].lc=0;
175 update(y);
176 update(root);
177 }
178
179 int Find(int w){// w
180 int x=Get(w);
181 splay(x,0);
182 return a[a[x].lc].size;
183 }
184
185 int Findkth(int x,int k){// x ， k
186 int s=a[a[x].lc].size;
187 if (k==s+1) return a[x].data;
188 if (s>=k) return Findkth(a[x].lc,k);
189 else return Findkth(a[x].rc,k-s-1);
190 }
191
192 int getpre(int w){
193 int y=Get(w);
194 Insert(w);
195 if (y!=-1) splay(y,0);
196 int ans=Getmax(a[root].lc);
197 Delet(w);
198 return a[ans].data;
199 }
200
201 int getne(int w){
202 Insert(w);
203 int ans=Getmin(a[root].rc);
204 Delet(w);
205 return a[ans].data;
206 }
207 int main(){
208 root=tot=0;
209 Insert(-50000000);
210 Insert(50000000);
211 scanf("%d",&q);//
212 while (q--){
213 int x,k;
214 scanf("%d%d",&x,&k);
215 if (x==1) Insert(k);
216 else if (x==2) Delet(k);
217 else if (x==3) printf("%d
",Find(k));
218 else if (x==4) printf("%d
",Findkth(root,k+1));
219 else if (x==5) printf("%d
",getpre(k));
220 else if (x==6) printf("%d
",getne(k));
221 }
222 return 0;
223 }좋은 웹페이지 즐겨찾기
