FHQ Treap是著名OI选手范浩强发明的一种平衡树。其高明之处是所有的操作都只用到了分裂和合并这两个基本操作。这两个基本操作的复杂度都为$O(logn)$。
节点定义 ：

  struct node{
    int ls,rs;    //存储左右孩子节点下标
    int key,
pri;  //存储节点关键值以及优先级
    int size;     //以该节点为根的节点数量
  } tree[N];

分裂 ：

void split(int u,int k, int& L,int& R)

将一棵以u为根Treap按键值分裂，返回分别以L，R为根的两棵树，其中L，R按引用传递。其中左树L上所有节点的键值都小于等于k，右树R上所有节点的键值都大于k。

分裂.gif

void split(int u, int k, int& L, int& R)
{
  if(u == 0)
  {L = R = 0; return;}
  if(tree[u].key < k)
  {
    L = u;
    split(tree[u].rs, k, tree[L].rs, R);
  }else
  {
    R = u;
    split(tree[u].ls, k, L, tree[R].ls);
  }
  pushup(u);
}

下面进行一下详细的解释，若节点u的键值小于等于x，则说明节点u以及其左子树可分裂到左树L中，故 L = u 。由于u中右子树上待分裂节点的键值必然大于目前左树L上节点的键值，后面即使要分裂到左树L上，也只能分裂的L的右子树上。故 split(tree[u].rs, k, tree[L].rs, R) 。同理，我们也可以解释分裂到右树R上的情况。

合并 ：
int merge(int L,int R)
将两棵分别以L，R为根的树，合并为一棵树，并返回合并后的根节点。

合并.gif

上图中，节点内部数据为二元组(关键值$key$,优先级$pri$)。若节点$L$的优先级小，根据优先级堆的性质，则$L$应作为合并后树的根。根据关键值二叉树性质，$L$左子树可保持不变。只需递归处理$L$的右子树与$R$合并的为$L$右子树的过程。
若节点$R$的优先级小，根据优先级堆的性质，则$R$应作为合并后树的根。根据关键值二叉树性质，$R$右子树可保持不变。只需递归处理$L$与$R$左子树合并为$R$左子树的过程。
每次递归只处理左右子树一个分支，所以时间复杂度为$O(logn)$, 且由于$pri$是随机数值合并后的树也会相对平衡。

int merge(int L,int R)
{
    if(!L||!R)return L+R;
    if(tree[L].pri < tree[R].pri)
    {
        tree[L].rs = merge(tree[L].rs, R);
        pushup(L);return L;
    }
    else
    {
        tree[R].ls = merge(L,tree[R].ls);
        pushup(R);return R;
    }
}

接下来还有getkth 

int getkth(int k){
    int p = root;
    while(p){
        //if(fhq[p].tag) pushdown(p);
        if(fhq[fhq[p].l].size + 1 == k) break;

        if(k <= fhq[fhq[p].l].size){
            p = fhq[p].l;
        }else{
            k -= fhq[fhq[p].l].size + 1;
            p = fhq[p].r;
        }
    }
    return fhq[p].val;
}

删除某位置数据 

int remove(int k){
    int x,y,del;
    split(root, k, x, y);
    split(x, k - 1, x, del);
    root = merge(x , y);
    return fhq[del].val;
}