萌新 30pts 求助
查看原帖
萌新 30pts 求助
610557
shinzanmonoszm 妹妹楼主2023/1/25 12:57
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<random>
std::mt19937 rnd(20220121);
const int sz = 1e5 + 10;
const int inf = 0x3fffffff;
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();
        ++tree[pos].size;
        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) rotateleft(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 lessRank(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 + lessRank(tree[pos].rson, val);
        else return lessRank(tree[pos].lson, val);
    }
    int greaterRank(int pos, int val) {
        if (pos == 0) return 0;
        if (val == tree[pos].val) return tree[tree[pos].rson].size + 1;
        else if (val < tree[pos].val)
            return tree[tree[pos].rson].size + tree[pos].cnt + greaterRank(tree[pos].lson, val);
        else return greaterRank(tree[pos].rson, val);
    }
} less, greater;
int change(int a, int b, int c) {
    if (a > 0) return std::floor(1. * (c - b) / a) + 1;
    else return std::ceil(1. * (c - b) / a) - 1;
}
int a[sz], b[sz], c[sz], isdel[sz], val[sz];
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, cnt = 0;
    std::cin >> n;
    for (int i = 1, j = 0; i <= n; i++) {
        std::string op;
        int k;
        std::cin >> op;
        if (op == "Add") {
            ++j;
            std::cin >> a[j] >> b[j] >> c[j];
            if (a[j] == 0) {
                if (b[j] > c[j]) cnt++;
                continue;
            }
            val[j] = change(a[j], b[j], c[j]);
            if (a[j] > 0) greater.insert(greater.root, val[j]);
            else less.insert(less.root, val[j]);
        } else if (op == "Del") {
            std::cin >> k;
            if (isdel[k] == inf) continue;
            if (a[k] == 0 && b[k] > c[k]) cnt--;
            else if (a[k] > 0) greater.erase(greater.root, val[k]);
            else less.erase(less.root, val[k]);
            isdel[k] = inf;
        } else {
            std::cin >> k;
            int res = 0;
            res += greater.lessRank(greater.root, k);
            res += less.greaterRank(less.root, k);
            std::cout << res + cnt << "\n";
        }
    }
    return 0;
}
2023/1/25 12:57
加载中...