fhq treap 封装

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ls (l[cnt])
#define rs (r[cnt])
const int N = 100005;

struct Ftree
{
    int l[N], r[N], val[N], rad[N], siz[N], ecnt, rt;
    int New(int k)
    {
        val[++ecnt] = k;
        rad[ecnt] = rand();
        siz[ecnt] = 1;
        return ecnt;
    }
    void update(int cnt)
    {
        siz[cnt] = siz[ls] + siz[rs] + 1;
    }
    void split(int cnt, int k, int &x, int &y)
    {
        if(cnt == 0)
        {
            x = y = 0;
            return ;
        }
        if(val[cnt] <= k)
        {
            x = cnt;
            split(rs, k, rs, y);
        }
        if(val[cnt] > k)
        {
            y = cnt;
            split(ls, k, x, ls);
        }
        update(cnt);
    } 
    int merge(int x, int y)
    {
        if(x == 0) return y;
        if(y == 0) return x;
        if(rad[x] <= rad[y])
        {
            r[x] = merge(r[x], y);
            update(x);
            return x;
        }
        if(rad[x] > rad[y])
        {
            l[y] = merge(x, l[y]);
            update(y);
            return y;
        }
    }
    int kth(int cnt, int k)
    {
        if(siz[ls] + 1 == k) return val[cnt];
        if(siz[ls] >= k) return kth(ls, k);
        else return kth(rs, k - siz[ls] - 1);
    }
    void add(int k)
    {
        int x, y;
        split(rt, k, x, y);
        rt = merge(merge(x, New(k)), y);
    }
    void del(int k)
    {
        int x, y, z;
        split(rt, k, x, y);
        split(x, k - 1, x, z);
        z = merge(l[z], r[z]);
        rt = merge(merge(x, z), y);
    }
    int suc(int k)
    {
        int x, y, ans; 
        split(rt, k, x, y);
        ans = kth(y, 1);
        rt = merge(x, y);
        return ans;
    }
    int pre(int k)
    {
        int x, y, ans;
        split(rt, k - 1, x, y);
        ans = kth(x, siz[x]);
        rt = merge(x, y);
        return ans;
    }   
}ft;
int main()
{

}