萌新刚学 Treap 求调
查看原帖
萌新刚学 Treap 求调
610557
shinzanmonoszm 妹妹楼主2023/1/22 01:33
#include<iostream>
#include<algorithm>
#include<cmath>
#include<random>
std::mt19937 rnd(20220121);
const int sz = 1e5 + 10;
struct BST {
    struct node {
        int val, lson, rson, cnt, size;
        unsigned key;
        node& operator^=(const int v) {
            val = v;
            key = rnd();
            size = cnt = 1;
            return *this;
        }
    } tree[sz];
    int num, root;
    void resize(int p) {
        tree[p].size = tree[p].cnt + tree[tree[p].lson].size + tree[tree[p].rson].size;
    } 
    void rotateleft(int &p) {
        int tmp = tree[p].rson;
        tree[p].rson = tree[tmp].lson;
        tree[tmp].lson = p;
        tree[tmp].size = tree[p].size;
        resize(p);
        p = tmp; 
    }
    void rotateright(int &p) {
        int tmp = tree[p].lson;
        tree[p].lson = tree[tmp].rson;
        tree[tmp].rson = p;
        tree[tmp].size = tree[p].size;
        resize(p);
        p = tmp;
    }
    void insert(int &pos, int val) {
        if (pos == 0) return pos = ++num, tree[pos] ^= val, void();
        if (val == tree[pos].val) tree[pos].size++, tree[pos].cnt++;
        else if (val < tree[pos].val) {
            insert(tree[pos].lson, val);
            if (tree[pos].key > tree[tree[pos].lson].key) rotateright(pos);
        } else if (val > tree[pos].val) {
            insert(tree[pos].rson, val);
            if (tree[pos].key < tree[tree[pos].rson].key) rotateright(pos);
        }
    }
    bool erase(int &pos, int val) {
        if (pos == 0) return false;
        if (val < tree[pos].val) {
            bool successErase = erase(tree[pos].lson, val);
            if (successErase) tree[pos].size--;
            return successErase;
        } else if (val > tree[pos].val) {
            bool successErase = erase(tree[pos].rson, val);
            if (successErase) tree[pos].size--;
            return successErase;
        } else {
            if (tree[pos].cnt > 1) return tree[pos].cnt--, tree[pos].size--, true;
            if (tree[pos].lson && tree[pos].rson) {
                if (tree[tree[pos].lson].key < tree[tree[pos].rson].key)
                    return rotateright(pos), erase(pos, val);
                else return rotateleft(pos), erase(pos, val);
            } else {
                pos = tree[pos].lson | tree[pos].rson;
                return true;
            }
        }
    }
    int rank(int pos, int val) {
        if (pos == 0) return 0;
        if (val == tree[pos].val) return tree[tree[pos].lson].size + 1;
        else if (val > tree[pos].val)     
            return tree[tree[pos].lson].size + tree[pos].cnt + rank(tree[pos].rson, val);
        else return rank(tree[pos].lson, val);
    }
} less, greater;
std::pair<int, bool> change(int a, int b, int c) {
    if (a > 0) return std::make_pair((c - b) / a, 1);
    else return std::make_pair(std::ceil(1. * (c - b) / a), 0);
}
std::pair<int, bool> equ[sz];
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, cnt = 0;
    std::cin >> n;
    for (int i = 1; i <= n; i++) {
        std::string op;
        int a, b, c, k;
        std::cin >> op;
        if (op == "Add") {
            std::cin >> a >> b >> c;
            if (a == 0) {
                if (b > c) cnt++;
                continue;
            }
            equ[i] = change(a, b, c);
            if (equ[i].second) greater.insert(greater.root, equ[i].first);
            else less.insert(less.root, equ[i].first);
        } else if (op == "Del") {
            std::cin >> k;
            if (equ[k].first == -0x7fffffff) continue;
            if (equ[k].second) greater.erase(greater.root, equ[k].first);
            else less.erase(less.root, equ[k].first);
            equ[k].first = -0x7fffffff;
        } else {
            std::cin >> k;
            int res = 0;
            res += less.tree[less.root].size - less.rank(less.root, k);
            int num = greater.rank(greater.root, k);
            res += num;
            if (num != 0) res--;
            std::cout << res + cnt << "\n";
        }
    }
    return 0;
}

2023/1/22 01:33
加载中...