看题解里没有写 fhq 的，来贡献一发 fhq 题解。

首先，fhq treap 可以很轻松维护知排名，求点的编号及用户编号，但不能很好的维护知用户编号来排名。我们先解决这个问题。

我们可以额外维护一个节点信息，就是每个点的父亲。如果我们知道了一个节点编号 $x$，根据 BST 的性质，则它的左子树应该排名都小于它，如果它是它父亲的右儿子，则它的父亲与它的左兄弟排名也小于它，根据每棵子树的大小信息，就可以递归求解出知节点编号求排名的问题。

如果我们知道的是用户编号而不是节点编号，只用拿 map 对用户编号和节点编号做一个映射即可。

但是这道题 $n \le 10^8$，不能插入这么多节点。原来每个节点都存一个用户编号，现在我们需要维护一段连续的用户编号即可。具体细节看代码。

创建一个新的节点，我们取用户编号连续段的左端点作为和节点编号做映射。由于存的是连续段，sz(x) 取值为连续段的长度。

int New(int l, int r){
    mp[l] = ++tot;
    rd(tot) = rand(); sz(tot) = r-l+1;
    l(tot) = l; r(tot) = r;
    return tot;
}

push_up 的时候额外维护 fa 信息

void push_up(int x){
    sz(x) = sz(ls(x))+sz(rs(x))+len(x);
    fa(ls(x)) = fa(rs(x)) = x;
}

merge 没什么区别，split 要注意，当前节点的 sz 不再为一

int merge(int x, int y){
    if (!x || !y) return x|y;
    if (rd(x) > rd(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 (sz(ls(p)) >= k){
        y = p;
        split(ls(p),k,x,ls(y));
    }else{
        x = p;
        split(rs(p),k-sz(ls(p))-len(p),rs(x),y); // len(x) = r(x)-l(x)+1;
    }
    push_up(p);
}

需要注意，这里的 k-sz(ls(p))-len(p) 不会出现是负数的情况，我们不会将一个节点中的连续编号再次分裂，如果有需要分裂一个节点，会先分裂节点，再调用此函数。

知排名求用户编号：

int find_kth(int x, int rk){
    if (rk <= sz(ls(x))) return find_kth(ls(x),rk); // 递归左边
    rk -= sz(ls(x));
    if (rk <= len(x)) return l(x)+rk-1;
    // 如果在这个节点所代表的连续编号里，那么答案就等于区间左端点
    // 所代表的用户编号加上排名再 -1
    return find_kth(rs(x),rk-len(x)); 
    // 相当于减去 sz(ls(x)) 与 len(x) 递归右边
}

知节点编号求排名：（求的是节点代表连续用户编号右端点的排名）

int find_rk(int x){
    int res = sz(ls(x))+len(x); 
    // 它的左子树和它自身右端点左边的编号排名比它小
    while(x != rt && x){ // 一直循环到根
        if (rs(fa(x)) == x) res += sz(ls(fa(x)))+len(fa(x));
        // 它是右子树，父亲和左兄弟都比它小
        x = fa(x);
    }
    return res;
}

删除插入一段区间：

void erase(int l, int r){
    int x,y,z;
    split(rt,l-1,x,y);
    split(y,r-l+1,y,z);
    rt = merge(x,z);
}
void insert(int p, int l, int r){
    int x,y;
    split(rt,p-1,x,y);
    rt = merge(x,merge(New(l,r),y));
}

主函数：

while(m--){
    int opt,x,y;
    cin >> opt;
    if (opt == 4){
        int rk;
        cin >> rk;  rk -= lst;
        cout << (lst = find_kth(rt,rk)) << endl;
        continue;
    }
    cin >> x; x -= lst;
    if (opt == 1){
        cin >> y; y -= lst;
    }
    auto it = --mp.upper_bound(x);
    int l = (*it).fi, p = (*it).se;
    int r = r(p);
    // 找到用户编号所对应的节点编号，以及节点对应的连续用户编号段的左右端点
    
    
    cout << (lst = find_rk(p)-(r-x)) << endl;
    // 排名是 连续用户段右端点的排名减去 (右端点到编号 x 的距离)
    
    erase(lst-(x-l),lst+(r-x));
    // 将这个段删去

    if (x > l) insert(lst-(x-l),l,x-1);
    if (x < r) insert(lst,x+1,r);
    if (opt == 1) insert(lst,y,y);
    if (opt == 2) insert(1,x,x);
    if (opt == 3) insert(n,x,x);
    
    // 依题意插入新段即可
}