普通Treap求助玄学错误
查看原帖
普通Treap求助玄学错误
677124
picha楼主2023/2/10 21:30

交上去WA#4,MLE#5-10,下载了第4个点,结果本地测是对的,已调崩溃,求助大佬

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 100000;
const ll N = maxn * 2 + 10;
struct nde{
    ll val, rnd, siz, l, r;
};
struct treap{
    ll cnt, rt;
    nde a[N];
    void clr() {
        cnt = 0;
        rt = 0;
    }
    void pushup(ll x) {
        a[x].siz = a[a[x].l].siz + a[a[x].r].siz + 1;
    }
    ll new_nde(ll k) {
        ++cnt;
        a[cnt].val = k;
        a[cnt].rnd = rand();
        a[cnt].siz = 1;
        a[cnt].l = 0;
        a[cnt].r = 0;
        return cnt;
    }
    void lrtt(ll &x) {
        ll k = a[x].r;
        a[x].r = a[k].l;
        a[k].l = x;
        pushup(x);
        pushup(k);
        x = k;
    }
    void rrtt(ll &x) {
        ll k = a[x].l;
        a[x].l = a[k].r;
        a[k].r = x;
        pushup(x);
        pushup(k);
        x = k;
    }
    void insrt(ll &x, ll k) {
        if (x == 0) {
            x = new_nde(k);
            return;
        }
        if (k < a[x].val) {
            insrt(a[x].l, k);
            pushup(x);
            if (a[x].rnd < a[a[x].l].rnd) {
                rrtt(x);
            }
        }
        else {
            insrt(a[x].r, k);
            pushup(x);
            if (a[x].rnd < a[a[x].r].rnd) {
                lrtt(x);
            }
        }
    }
    void remve(ll &x, ll k) {
        if (a[x].val == k) {
            if (a[x].l == 0 && a[x].r == 0) {
                x = 0;
            }
            else if (a[x].l > 0) {
                x = a[x].l;
            }
            else if(a[x].r > 0) {
                x = a[x].r;
            }
            else {
                if (a[a[x].l].rnd < a[a[x].r].rnd) {
                    lrtt(x);
                    remve(a[x].l, k);
                }
                else {
                    rrtt(x);
                    remve(a[x].r, k);
                }
            }
            return;
        }
        if (a[x].val > k) {
            remve(a[x].l, k);
        }
        else {
            remve(a[x].r, k);
        }
        pushup(x);
    }
    ll get_rank(ll x, ll k) {
        if (x == 0) {
            return 0;
        }
        if (k <= a[x].val) {
            return get_rank(a[x].l, k);
        }
        else {
            return (get_rank(a[x].r, k) + a[a[x].l].siz + 1);
        }
    }
    ll get_val(ll x, ll k) {
        if (k <= a[a[x].l].siz) {
            return get_val(a[x].l, k);
        }
        else if (k == a[a[x].l].siz + 1) {
            return a[x].val;
        }
        else {
            return get_val(a[x].r, k - a[a[x].l].siz - 1);
        }
    }
    ll get_pre(ll x, ll k) {
        if (x == 0) {
            return 0;
        }
        if (k <= a[x].val) {
            return get_pre(a[x].l, k);
        }
        else {
            ll y = get_pre(a[x].r, k);
            if (y == 0) {
                return a[x].val;
            }
            else {
                return y;
            }
        }
    }
    ll get_suf(ll x, ll k) {
        if (x == 0) {
            return 0;
        }
        if (k >= a[x].val) {
            return get_suf(a[x].r, k);
        }
        else {
            ll y = get_suf(a[x].l, k);
            if (y == 0) {
                return a[x].val;
            }
            else {
                return y;
            }
        }
    }
}st;
ll n, m;
int main() {
    scanf("%lld", &n);
    st.clr();
    for (ll i = 1; i <= n; ++i) {
        ll opt, x, ans;
        scanf("%lld%lld", &opt, &x);
        if (opt == 1) {
            st.insrt(st.rt, x);
        }
        else if (opt == 2) {
            st.remve(st.rt, x);
        }
        else if (opt == 3) {
            ans = st.get_rank(st.rt, x) + 1;
            printf("%lld\n", ans);
        }
        else if (opt == 4) {
            ans = st.get_val(st.rt, x);
            printf("%lld\n", ans);
        }
        else if (opt == 5) {
            ans = st.get_pre(st.rt, x);
            printf("%lld\n", ans);
        }
        else if (opt == 6) {
            ans = st.get_suf(st.rt, x);
            printf("%lld\n", ans);
        }
    }
    return 0;
}
2023/2/10 21:30
加载中...