可以支援的操作：
- 插入 xxx 數
- 删除 xxx 數(若有多個相同的數，因隻删除一個)
- 查詢 xxx 數的排名(排名定義為比目前數小的數的個數 +1 。若有多個相同的數，因輸出最小的排名)
- 查詢排名為 xxx 的數
- 求 xxx 的前驅(前驅定義為小于 xxx ，且最大的數)
- 求 xxx 的後繼(後繼定義為大于 xxx ，且最小的數)
7.來維護一個有序數列，其中需要提供以下操作：翻轉一個區間，例如原有序序列是5 4 3 2 1，翻轉區間是[2,4]的話，結果是5 2 3 4 1
0.預備：
struct有：siz,sum（該點出現次數）,fa,val,以及ch[0],ch[1]
const int N=100000+10;
const int inf=0x3f3f3f3f;
int n,m;
struct node{
int siz,sum,val,fa;
int ch[2];
}t[N];
int pc,dc,dp[N];
int root; 1.pushup，新節點，回收節點
void pushup(int x){
t[x].siz=t[t[x].ch[0]].siz+t[t[x].ch[1]].siz+t[x].sum;
}
int newnode(int v,int f){
int r=dc?dp[dc--]:++pc;
memset(t+r,0,sizeof (node));
t[r].siz=1,t[r].sum=1,t[r].fa=f,t[r].val=v;
return r;
}
void del(int x){
dp[++dc]=x;
} 2.rotate(x)，與父親旋轉。注意每一步的轉移，注意最後pushup(y)
void rotate(int x){
int y=t[x].fa,d=t[y].ch[1]==x;
t[t[y].ch[d]=t[x].ch[d^1]].fa=y;
t[t[x].fa=t[y].fa].ch[t[t[y].fa].ch[1]==y]=x;
t[x].ch[d^1]=y,t[y].fa=x;
pushup(y);
} 3.splay(x,f)，旋轉到f的兒子，雙旋操作，一次考慮兩個節點。注意，無論如何，rotate(x)，無論如何，pushup(x)，如果f=0，root=x
void splay(int x,int f){
while(t[x].fa!=f){
int y=t[x].fa,z=t[y].fa;
if(z!=f){
rotate(((t[z].ch[0]==y)==(t[y].ch[0]==x))?y:x);
}
rotate(x);
}
pushup(x);
if(f==0) root=x;
} 4.insert(val)，注意找到相同的值之後，break掉，注意每次都要splay到根（雖然資料水，不旋更快），理論保證樹高。
void insert(int val){
if(!root){
root=newnode(val,0);
return;
}
int u=root;
while(1){
t[u].siz++;
if(t[u].val==val){
t[u].sum++;
break;
}
int d=t[u].val<val;
if(!t[u].ch[d]){
t[u].ch[d]=newnode(val,u);
u=t[u].ch[d];
break;
}
u=t[u].ch[d];
}
//splay(u,0);
} 5.dele(val)，步驟：先找到val,旋轉到根，再找到根節點右子樹最小值，即root的後繼，splay到根的兒子（必然是右兒子），再删掉root，改root為右兒子
需要特判：右子樹不存在？直接将左二子當做新根。删掉的是最後一個值?我這個代碼不怕，root會直接變成0
void dele(int val){
int goal=root,son=0;
while(1){
if(t[goal].val==val) break;
goal=t[goal].ch[t[goal].val<val];
}
t[goal].sum--;
splay(goal,0);
t[goal].siz--;
if(t[goal].sum>0) return;
son=t[goal].ch[1];
while(son&&t[son].ch[0]){
son=t[son].ch[0];
}
if(son){
splay(son,root);
t[son].ch[0]=t[root].ch[0];
t[t[root].ch[0]].fa=son;
del(root);
root=son;
t[son].fa=0;
pushup(son);
}
else{
root=t[goal].ch[0];
t[root].fa=0;
del(goal);
}
} 6.rank(x)，同treap
7.kth(k)，同treap
8.front(x)，同treap
9.back(x)，同treap
int rank(int val){
int u=root;
int ret=1;
while(u){
if(t[u].val<val) {
ret+=t[t[u].ch[0]].siz+t[u].sum;
u=t[u].ch[1];
}
else if(t[u].val==val) {ret+=t[t[u].ch[0]].siz;break;}
else u=t[u].ch[0];
}
return ret;
}
int kth(int k){
int u=root;
while(1){
if(!u) return 0;
int d=k-t[t[u].ch[0]].siz;
if(d<=0) u=t[u].ch[0];
else if(d>=1&&d<=t[u].sum) return t[u].val;
else {
k=d-t[u].sum;
u=t[u].ch[1];
}
}
}
int front(int val){
int u=root;
int ret=-inf;
while(u){
if(t[u].val<val){
ret=max(ret,t[u].val);
u=t[u].ch[1];
}
else {
u=t[u].ch[0];
}
}
return ret;
}
int back(int val){
int u=root;
int ret=inf;
while(u){
if(t[u].val>val){
ret=min(ret,t[u].val);
u=t[u].ch[0];
}
else{
u=t[u].ch[1];
}
}
return ret;
} 10.pushdown(x)，翻轉其實就是不停地交換節點的兩個子樹。因為在每次通路到這個節點的時候，尤其在splay的時候，必然會啟動pushdown，是以，翻轉最終一定會都實作。下放旋轉标記，經常勤調用，要記得。
11.work(l,r)，處理旋轉操作，這裡，為了避免l=1，r=n的情況，放置1，n+2兩個哨兵，每個節點的編号實際上是編号減一。最後輸出要減一。
這個方法是針對1~n的排列，如果不是，最好是特判，其實加哨兵也是可以的。
實作的時候，先找到kth(l)也就是第k大的值，展現在中序周遊裡就是這個點的編号。當然，其實找的是l-1，但是由于編号是從2開始的。
将l旋轉到根。
同理,r=kth(r+2)。
将r旋轉到根節點的兒子（必然是右兒子）
這樣，根節點的右兒子的左子樹就是所求區間。
12.write(o)，記得pushdown，輸出的編号一定要在[2,n+1]内，因為1,n+2都是哨兵。按照中序周遊輸出即可
對于一個需要維護區間操作的平衡樹來說，每個節點的排序方式是編号大小，也就是中序周遊的節點編号一定是一個從1~n的單增序列。保證可以取l-1到根節點，r+1到根節點的兒子，就可以取出[l,r]了。
注意事項：
1.rotate裡面的壓行，不要記錯，不行就手寫。其實，第一行換兒子，第二行改父親，第三行改兩點之間的關系。
2.插入元素的時候，如果用while1循環，記得每到一個節點， 那麼這個節點的總的siz必然要加一，不論是新指派，還是多了一個新值。
3.插入元素的時候，如果找到了這個值，那麼就要break，不能繼續走了。
while(son&&t[son].ch[0]){
son=t[son].ch[0];
} ![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)