[HTML_REMOVED]

Think Functional!

要学FHQ Treap，首先要理解什么是FHQ。
所谓的”FHQ”，就是(范浩强)非旋的意思。
代表这种平衡树不需要依靠旋转来保持平衡。
事实上，FHQ Treap依靠分裂和合并来维持平衡性质。
所以我们称FHQ Treap为函数式Treap(即:不对现有的数据进行任何修改,仅仅是用历史数据来计算出新的)。
下面就来介绍一下这两个操作:
1.分裂:
所谓的”分裂”,就是将一颗FHQ Treap分成两颗，每一颗都满足FHQ Treap的性质。
其实很简单，就是一个递归求解的过程。
定义split(p,k,&x,&y),代表将以p为根的子树分为两个部分，其根分别为x,y。
这种分裂应满足:
以x为根的FHQ Treap的size域不大于k。
图例:

void split(int p,int k,int &x,int &y)
{
    if(!p){x=y=0;return;}
    push_down(p);
    if(tls(p).size<k){x=p;split(rs(x),k-tls(p).size-1,rs(x),y);}
    else{y=p;split(ls(y),k,x,ls(y));}
    push_up(p);
}

2.合并:
所谓的合并，就是将两颗FHQ Treap合为一颗。
也是一个递归的过程。
规定merge(x,y)返回的是将根为x,y的两棵树合并后的根。
图例:

int merge(int x,int y)
{
    if(!x||!y)return x+y;
    push_down(x);push_down(y);
    if(t(x).rnd<t(y).rnd){rs(x)=merge(rs(x),y);push_up(x);return x;}
    else{ls(y)=merge(x,ls(y));push_up(y);return y;}
}

例题:
acwing P253. 。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<climits>
#include<cstdlib>
#include<ctime>
#include<algorithm>
#include<complex>
#include<iostream>
#include<map>
#include<queue>
#include<vector>
#define ll long long
#define INF 2147483647
#define ls(p) t[p].ls
#define rs(p) t[p].rs
#define fa(p) t[p].fa
#define rnd(p) t[p].rnd
#define size(p) t[p].size
#define val(p) t[p].val
#define mid ((l+r)>>1)
using namespace std;
struct node
{
    int ls,rs;
    int size,rnd,val;
}t[1000010<<5];
int cnt,root;
void push_up(int p){size(p)=size(ls(p))+size(rs(p))+1;}
void new_node(int &k,int x){k=++cnt;val(k)=x;size(k)=1;rnd(k)=rand();ls(k)=rs(k)=0;k=cnt;}
int merge(int x,int y)
{
    if(!x||!y)return x|y;
    if(rnd(x)>rnd(y)){rs(x)=merge(rs(x),y);push_up(x);return x;}
    else{ls(y)=merge(x,ls(y));push_up(y);return y;}
}
void split(int p,int k,int &x,int &y)
{
    if(!p){x=y=0;return;}
    if(val(p)<=k){x=p;split(rs(x),k,rs(x),y);push_up(x);}
    else{y=p;split(ls(y),k,x,ls(y));push_up(y);}
}
void pop(int &root,int w){int x=0,y=0,z=0;split(root,w,x,z);split(x,w-1,x,y);y=merge(ls(y),rs(y));root=merge(merge(x,y),z);}
void push(int &root,int w){int x=0,y=0,z=0;split(root,w,x,y);new_node(z,w);root=merge(merge(x,z),y);}
int atrank(int p,int w)
{
    if(w==size(ls(p))+1)return val(p);
    else if(w<=size(ls(p)))return atrank(ls(p),w);
    else return atrank(rs(p),w-size(ls(p))-1);
}
int rnk(int &root,int w){int x,y;split(root,w-1,x,y);int ans=size(x)+1;root=merge(x,y);return ans;}
int pre(int &root,int w){int x,y,k,ans;split(root,w-1,x,y);if(!x)return -INF;k=size(x);ans=atrank(x,k);root=merge(x,y);return ans;}
int next(int &root,int w){int x,y,ans;split(root,w,x,y);if(!y)return INF;else ans=atrank(y,1);root=merge(x,y);return ans;}
int main()
{
    srand(224144);
    int n,op,w;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d%d",&op,&w);
        if(op==1)push(root,w);
        if(op==2)pop(root,w);
        if(op==3)printf("%d\n",rnk(root,w));
        if(op==4)printf("%d\n",atrank(root,w));
        if(op==5)printf("%d\n",pre(root,w));
        if(op==6)printf("%d\n",next(root,w));
    }
    return 0;
}