BZOJ 3224 Tyvj 1728 普通平衡树 - c++编程基础

Splay入门题。。。断断续续写了几天。。。。

自己写的常数好大。。。。。

3224: Tyvj 1728 普通平衡树

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 862 Solved: 351
[Submit][Status]

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

Source

平衡树

[Submit][Status]

#include 
  
   
#include 
   
     #include 
    
      #include 
      #include 
      
        using namespace std; #define Key_value (ch[ch[root][1]][0]) const int maxn=110100; const int INF=0x3f3f3f3f; int pre[maxn],ch[maxn][2],key[maxn],s[maxn]; int root,tot1; map
       
         nct; /************debug*********************/ void showit(int x) { if(x) { showit(ch[x][0]); cout<<"节点："<
        
         0) { Splay(r,0); push_up(r); } else if(nct[x]<=0) { Splay(r,0); nct.erase(x); int rt=Find_Max(ch[root][0]); if(rt) { Splay(rt,root); pre[rt]=pre[root]; ch[0][ch[0][1]==root]=rt; pre[ch[root][1]]=rt; ch[rt][1]=ch[root][1]; root=rt; } else { if(ch[root][1]) { pre[ch[root][1]]=0; ch[0][ch[0][1]==root]=ch[root][1]; root=ch[root][1]; } else init(); } push_up(root); } } int get_rank(int x) { int r=root,temp=0; while(ch[r][key[r]<=x]) { if(key[r]==x) break; if(key[r]<=x) temp+=s[r]-s[ch[r][1]]; r=ch[r][key[r]<=x]; } return s[ch[r][0]]+1+temp; } int get_pre(int x) { int ret=-INF; int r=root; while(r) { if(key[r]
         
          x) { ret=min(ret,key[r]); r=ch[r][0]; } else r=ch[r][1]; } return ret; } int get_kth(int x) { int r=root; while(true) { int left=s[ch[r][0]],right=s[ch[r][0]]+nct[key[r]]+1; if(x>left&&x
          
           =right) { r=ch[r][1]; x-=right-1; } } } int main() { int T_T; while(scanf("%d",&T_T)!=EOF) { init(); int a,b; for(int i=0;i