FHQ_Treap 非递归形式（没什么用）

柠檬熟了 · 2023-11-25 09:15:00 · 个人记录

Merge 函数用的模拟栈，比较丑陋

鉴定为又长又慢

namespace Treap_N { //FHQ_Treap
    struct Node {
        int ch[2] = {0, 0}, v, cnt, s, rk=ran() % 114514, f;
    };  

    int rt = 0, tot = 0, ans = 0, OPR1[MAXN], OPR2[MAXN], OPR3[MAXN];
    Node T[MAXN];

    #define lc ch[0]
    #define rc ch[1]

    inline void clear(int x) {
        T[x].f = T[x].lc = T[x].rc = T[x].v = T[x].cnt = T[x].s = T[x].rk = 0;
    }

    inline void maintain (int x) {
        if (!x) return;
        T[x].s=T[T[x].lc].s+T[T[x].rc].s+T[x].cnt;
    }

    inline void Split_V (unsigned int r, int k, int &x, int &y) {
        #define LIM (T[r].v > k)
        clear(0);
        unsigned int p[2] = {0, 0}, RT = r;
        while (T[r].lc || T[r].rc) T[T[r].ch[!LIM]].f = r, r = T[r].ch[!LIM];
        if (!r) r = T[r].f;
        while (r != RT) {
            T[p[LIM]].f = r, T[r].ch[!LIM] = p[LIM], p[LIM] = r;
            maintain(p[0]), maintain(p[1]), r = T[r].f, maintain(r);
            //  if (LIM == (T[T[r].f].v > k)) while (LIM == (T[T[r].f].v > k) && r != RT) p[LIM] = r, r = T[r].f, maintain(r);
        }
        T[p[LIM]].f = r, T[r].ch[!LIM] = p[LIM], p[LIM] = r;
        maintain(x = p[0]), maintain(y = p[1]); 
    }

    inline int Merge (int rt1, int rt2) {
        if (!rt1 || !rt2) return rt1 | rt2;
        int Cnt = 0, Tmp;
        OPR1[++ Cnt] = rt1, OPR2[Cnt] = rt2, OPR3[Cnt] = (T[rt1].rk < T[rt2].rk) ? 1 : 2;
        while (rt1 && rt2) {
            if (T[rt1].rk < T[rt2].rk) OPR1[++ Cnt] = T[rt1].rc, OPR2[Cnt] = rt2, rt1 = T[rt1].rc, OPR3[Cnt - 1] = 1;
            else OPR1[++ Cnt] = rt1, OPR2[Cnt] = T[rt2].lc, rt2 = T[rt2].lc, OPR3[Cnt - 1] = 2;
        }
        Tmp = OPR1[Cnt] | OPR2[Cnt];
        for (int i = Cnt - 1; i >= 1; -- i) {
            if (OPR3[i] == 1) T[OPR1[i]].rc = Tmp, maintain(OPR1[i]), Tmp = OPR1[i];
            else T[OPR2[i]].lc = Tmp, maintain(OPR2[i]), Tmp = OPR2[i];
        }
        return Tmp;
    } 

    inline void ins (int v) { 
        int RTL, RTR;
        T[++ tot].v = v, T[tot].s = 1, T[tot].cnt = 1;
        Split_V (rt, v, RTL, RTR); 
        rt = Merge(Merge(RTL, tot), RTR);
    } 

    inline void del (int v) { // Make Sure id Exist
        int RTA, RTB, RTC, RTD;
        Split_V(rt, v, RTA, RTB);
        Split_V(RTA, v - 1, RTC, RTD);
        RTD = Merge(T[RTD].lc, T[RTD].rc);
        rt = Merge(Merge(RTC, RTD), RTB);
    }

    inline int find_rank (int v) {
        int Now = rt, Ans = 0;
        while (T[Now].lc || T[Now].rc) {
            if (T[Now].v < v) Ans += T[Now].cnt + T[T[Now].lc].s, Now = T[Now].rc;
            else Now = T[Now].lc;
        }
        if (Now && T[Now].v < v) ++ Ans;
        return Ans + 1;
    }

    inline int find_key (int x) { // Make Sure id Exist
        int Now = rt, Sz = T[Now].cnt + T[T[Now].lc].s;
        if (x < 1) return -2147483647;
        else if (x > T[Now].s) return 2147483647; 
        while (Sz != x) {
            if (Sz > x) Sz -= T[Now].cnt, Now = T[Now].lc, Sz -= T[T[Now].rc].s;
            else Now = T[Now].rc, Sz += T[Now].cnt + T[T[Now].lc].s;
        }
        return T[Now].v;
    }

    inline int find_pre (int v) {
        int RK = find_rank(v), V = find_key(RK);
        if (V >= v) return find_key(RK - 1);
        return V;
    }

    inline int find_nxt (int v) {
        int RK = find_rank(v + 1), V = find_key(RK);
        return V;
    }

};

Core Part

namespace Treap_N { //FHQ_Treap
    struct Node {
        int ch[2] = {0, 0}, v, cnt, s, rk=ran() % 114514, f;
    };  

    int rt = 0, tot = 0, ans = 0, OPR1[MAXN], OPR2[MAXN], OPR3[MAXN];
    Node T[MAXN];

    #define lc ch[0]
    #define rc ch[1]

    inline void clear(int x) {
        T[x].f = T[x].lc = T[x].rc = T[x].v = T[x].cnt = T[x].s = T[x].rk = 0;
    }

    inline void maintain (int x) {
        if (!x) return;
        T[x].s=T[T[x].lc].s+T[T[x].rc].s+T[x].cnt;
    }

    inline void Split_V (unsigned int r, int k, int &x, int &y) {
        #define LIM (T[r].v > k)
        clear(0);
        unsigned int p[2] = {0, 0}, RT = r;
        while (T[r].lc || T[r].rc) T[T[r].ch[!LIM]].f = r, r = T[r].ch[!LIM];
        if (!r) r = T[r].f;
        while (r != RT) {
            T[p[LIM]].f = r, T[r].ch[!LIM] = p[LIM], p[LIM] = r;
            maintain(p[0]), maintain(p[1]), r = T[r].f, maintain(r);
            //  if (LIM == (T[T[r].f].v > k)) while (LIM == (T[T[r].f].v > k) && r != RT) p[LIM] = r, r = T[r].f, maintain(r);
        }
        T[p[LIM]].f = r, T[r].ch[!LIM] = p[LIM], p[LIM] = r;
        maintain(x = p[0]), maintain(y = p[1]); 
    }

    inline int Merge (int rt1, int rt2) {
        if (!rt1 || !rt2) return rt1 | rt2;
        int Cnt = 0, Tmp;
        OPR1[++ Cnt] = rt1, OPR2[Cnt] = rt2, OPR3[Cnt] = (T[rt1].rk < T[rt2].rk) ? 1 : 2;
        while (rt1 && rt2) {
            if (T[rt1].rk < T[rt2].rk) OPR1[++ Cnt] = T[rt1].rc, OPR2[Cnt] = rt2, rt1 = T[rt1].rc, OPR3[Cnt - 1] = 1;
            else OPR1[++ Cnt] = rt1, OPR2[Cnt] = T[rt2].lc, rt2 = T[rt2].lc, OPR3[Cnt - 1] = 2;
        }
        Tmp = OPR1[Cnt] | OPR2[Cnt];
        for (int i = Cnt - 1; i >= 1; -- i) {
            if (OPR3[i] == 1) T[OPR1[i]].rc = Tmp, maintain(OPR1[i]), Tmp = OPR1[i];
            else T[OPR2[i]].lc = Tmp, maintain(OPR2[i]), Tmp = OPR2[i];
        }
        return Tmp;
    } 

    inline int find_rank (int v) {
        int Now = rt, Ans = 0;
        while (T[Now].lc || T[Now].rc) {
            if (T[Now].v < v) Ans += T[Now].cnt + T[T[Now].lc].s, Now = T[Now].rc;
            else Now = T[Now].lc;
        }
        if (Now && T[Now].v < v) ++ Ans;
        return Ans + 1;
    }

};