스 트 레 칭 트 리 기초 (Splay)

30973 단어 play
3224: Tyvj 1728 일반 밸 런 스 트 리
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 }

좋은 웹페이지 즐겨찾기