指针FHQ求助
  • 板块学术版
  • 楼主Tibrella
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/2/21 19:24
  • 上次更新2023/10/24 00:10:19
查看原帖
指针FHQ求助
655192
Tibrella楼主2023/2/21 19:24

如题,始终RE报空指针错,但是不会改了...

#include <iostream>
#include <random>

std::random_device seed;
std::mt19937 rd(seed());

using std::cin;
using std::cout;

#define endl '\n'
#define N 100514

class fhq_tree {
public:
    struct Node {
        Node *lc, *rc;
        int key, ext;
        int siz;

        void push_up() {
            siz = (lc ? lc->siz : 0) + (rc ? rc->siz : 0) + 1;  // 如果是叶子节点,siz 始终为 1,因此不需要在操作时更新叶子节点
        }
    } fhq[N * 2];

    Node* tail = fhq;
    Node* root = fhq + 1;
    fhq_tree() {fhq->lc = fhq->rc = root->lc = root->rc = fhq;}
    

    void ins(int v) {
        Node *l, *r;
        l = r = nullptr;
        Node* nod = new_node(v);
        split(root, v, l, r);
        root = merge(merge(l, nod), r);
    }

    void del(int v) {
        Node *l, *r, *del, *new_son;
        l = r = nullptr;
        split(root, v - 1, l, r);
        split(r, v, del, r);
        merge(del->lc, del->rc);
        root = merge(l, merge(new_son, r));
    }

    int get_rank(int v) {
        Node *l, *r;
        l = r = nullptr;
        split(root, v - 1, l, r);
        int res = l->siz + 1;
        root = merge(l, r);
        return res;
    }

    int get_kth(int v) {
        return kth(root, v)->key;
    }

    int get_front(int v) {
        Node *l, *r;
        l = r = nullptr;
        split(root, v - 1, l, r);
        int res = kth(l, l->siz)->key;
        merge(l, r);
        return res;
    }

    int get_next(int v) {
        Node *l, *r;
        l = r = nullptr;
        split(root, v, l, r);
        int res = kth(r, 1)->key;
        merge(l, r);
        return res;
    }

private:
    void split(Node* nod, int k, Node* l, Node* r) {  // 此处 l 指的是 l 树的右子树,r 指的是 r 树的左子树
        if (nod == nullptr) {                     // 此行实际上用来初始化
            l = r = nullptr;
            return;
        }

        if (nod->key <= k) {  // 键值比参照小,因而左子树所有值比参照小,分到 l 树,同时右子树未知,向右继续分裂
            l = nod;
            split(nod->rc, k, nod->rc, r);
           
        } else {
            r = nod;
            split(nod->lc, k, l, nod->lc);
            
        }
        std::cerr << nod << endl;
        exit(0);
        nod->push_up();
    }

    Node* merge(Node* l, Node* r) {
        if (l == nullptr) return r;
        if (r == nullptr) return l;
        std::cerr << ">>>>> fhq: " << fhq << " l: " << l << " r: " << r << endl; 
        if (l->ext < r->ext) {  // l 附加权值比 r 小,为了保证堆的性质需要让 r 在 l 底下,又因为 r 的真权值一定比 l 大,因此合并到右子树上
            l->rc = merge(l->rc, r);
            l->push_up();
            return l;
        } else {
            r->lc = merge(l, r->lc);
            r->push_up();
            return r;
        }
    }

    Node* new_node(int v) {
        ++tail;
        tail->lc = tail->rc = nullptr;
        tail->key = v;
        tail->siz = 1;
        tail->ext = rd();
        return tail;
    }
    Node* kth(Node* nod, int k) {  // 查找第 k 小的数字,分三种情况,即 k + 1 < nod->lc->size,k + 1 == nod->lc->size 和 k + 1 > nod->lc->size
        while (nod->lc->siz != k + 1) {
            while (!nod->lc) nod = nod->rc;
            if (nod->lc->siz > k + 1) {
                nod = nod->lc;
            } else {
                k -= nod->lc->siz+1;
                nod = nod->rc;
            }
        }
        return nod;
    }
};

fhq_tree tree;
int n;
int opt, x;

int main() {
    std::ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n;
    while (n--) {
        cin >> opt >> x;
        if (opt == 1) {
            tree.ins(x);
        } else if (opt == 2) {
            tree.del(x);
        } else if (opt == 3) {
            cout << tree.get_rank(x) << endl;
        } else if (opt == 4) {
            cout << tree.get_kth(x) << endl;
        } else if (opt == 5) {
            cout << tree.get_front(x) << endl;
        } else if (opt == 6) {
            cout << tree.get_next(x) << endl;
        }
    }

    return 0;
}

2023/2/21 19:24
加载中...