fhq-treap段错误求助
查看原帖
fhq-treap段错误求助
320697
AMIRIOX無暝楼主2021/2/19 21:11

样例就段错误了 然而调不出来呜呜呜呜

#include <cstdio>
#include <iostream>
#include <random>
using namespace std;
mt19937 rnd(233);
const int maxn = 10010;
struct node {
    int ls, rs;
    int val, size;
    int prikey;
} fhq[maxn];
int root, cnt;
int newnode(int val) {
    fhq[++cnt].val = val;
    fhq[cnt].prikey = rnd();
    fhq[cnt].size = 1;
    return cnt;
}
void update(int x) {
    fhq[x].size = fhq[fhq[x].ls].size + fhq[fhq[x].rs].size;
}
void split(int now, int key, int& x, int& y) {
    if (!now)
        x = y = 0;
    if (fhq[now].val <= key) {
        x = now;
        split(fhq[now].rs, key, fhq[now].rs, y);
    } else {
        y = now;
        split(fhq[now].ls, key, x, fhq[now].ls);
    }
    update(now);
}
int merge(int x, int y) {
    if (!x || !y)
        return x + y;
    if (fhq[x].prikey >= fhq[y].prikey) {
        fhq[x].rs = merge(fhq[x].rs, y);
        update(x);
        return x;
    } else {
        fhq[y].ls = merge(x, fhq[y].ls);
        update(y);
        return y;
    }
}
int x, y, z;
void insert(int val) {
    split(root, val, x, y);
    root = merge(merge(x, newnode(val)), y);
}
void del(int val) {
    split(root, val, x, z);
    split(x, val - 1, x, y);
    y = merge(fhq[y].ls, fhq[y].rs);
    root = merge(merge(x, y), z);
}
int getrank(int val) {
    split(root, val - 1, x, y);
    int res = fhq[x].size + 1;
    root = merge(x, y);
    return res;
}
int kth(int k) {
    int now = root;
    while (now) {
        if (fhq[now].size + 1 == k)
            break;
        else if (fhq[fhq[now].ls].size >= k)
            now = fhq[now].ls;
        else {
            k -= fhq[fhq[now].ls].size + 1;
            now = fhq[now].rs;
        }
    }
    return fhq[now].val;
}
int pre(int vg) {
    split(root, vg - 1, x, y);
    int now = x;
    while (fhq[now].rs) {
        now = fhq[now].rs;
    }
    int res = fhq[now].val;
    root = merge(x, y);
    return res;
}
int nxt(int vg) {
    split(root, vg, x, y);
    int now = y;
    while (fhq[now].ls) {
        now = fhq[now].ls;
    }
    int res = fhq[now].val;
    root = merge(x, y);
    return res;
}
int n, cmd, _x;
int main() {
    scanf("%d", &n);
    while (n--) {
        scanf("%d %d", &cmd, &_x);
        if (cmd == 1) {
            insert(_x);
        } else if (cmd == 2) {
            del(_x);
        } else if (cmd == 3) {
            printf("%d\n", getrank(_x));
        } else if (cmd == 4) {
            printf("%d\n", kth(_x));
        } else if (cmd == 5) {
            printf("%d\n", pre(_x));
        } else if (cmd == 6) {
            printf("%d\n", nxt(_x));
        }
    }
    return 0;
}
2021/2/19 21:11
加载中...