12111: 【原2111】最小差值

题目

题目描述

author: ftiasch 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/2111

Description

维护集合\( S\)，初始时为空集，支持\( 3\)种操作：

询问\( |x - a|\)的最小值，其中\( x \in S\)

插入元素 \( x\)

删除元素 \( x\)

Input Format

第\(1\)行，\(1\)个整数\(M\)，表示操作的数量。

接下来\(M\)行，每行描述一个操作，共有\(3\)种类型：

0 x, 询问要求的最小值

1 x, 插入元素\( x\)

2 x, 删除元素\( x\)

Output Format

对于每个询问，输出对应的最小值。

Sample Input

5
1 0
1 1
0 2
2 1
0 2

Sample Output

1
2

Specification

对于\(30\%\)的数据，\(1 \leq M \leq 1000\)。

对于\(100\%\)的数据，\(1 \leq M \leq 10^5, 0 \leq x \leq 10^8\)。保证不会插入重复的元素，不会删除不存在的元素，查询时集合至少有\(1\)个元素。

ligongzzz's solution

#include "iostream"
#include "cstdio"
#include "cmath"
#include "set"
#include "algorithm"
using namespace std;

int main() {
    set<int> setdata;
    int M;
    cin >> M;

    for (; M > 0; --M) {
        int op, x;
        scanf("%d %d", &op, &x);

        if (op == 0) {
            auto p=setdata.lower_bound(x);
            if (p == setdata.end())
                printf("%d\n", (int)abs(*setdata.rbegin() - x));
            else if (p == setdata.begin())
                printf("%d\n", (int)abs(*setdata.begin() - x));
            else {
                int x1 = (int)abs(*p - x),
                    x2 = (int)abs(*(--p) - x);
                printf("%d\n", min(x1, x2));
            }

        }
        else if (op == 1) {
            setdata.insert(x);
        }
        else {
            setdata.erase(setdata.find(x));
        }
    }
    return 0;
}

Neight99's solution

#include <cstring>
#include <iostream>

using namespace std;

int min(int a, int b) { return (a > b) ? b : a; }

class BinarySearchTree {
   private:
    struct Node {
        int data;
        Node *left;
        Node *right;

        Node(int x = 0, Node *l = 0, Node *r = 0)
            : data(x), left(l), right(r) {}
    };

    int sum;
    Node *root;
    void insert(int x, Node *&rht);
    void deleteNode(int x, Node *&rht);
    void deleteEqual(int x, Node *&rht);
    void find(int x, Node *&rht);
    void clear(Node *&rht);

   public:
    BinarySearchTree();
    ~BinarySearchTree();
    void insert(int x);
    void deleteEqual(int x);
    void find(int x);
    void findIth(int i);
    int findMin(int x);
};

BinarySearchTree::BinarySearchTree() : root(0), sum(0) {}

BinarySearchTree::~BinarySearchTree() { clear(root); }

void BinarySearchTree::clear(Node *&rht) {
    if (rht == 0) {
        return;
    }
    clear(rht->left);
    clear(rht->right);
    delete rht;
    sum--;
}

void BinarySearchTree::insert(int x) { insert(x, root); }

void BinarySearchTree::insert(int x, Node *&rht) {
    if (rht == 0) {
        rht = new Node(x);
        sum++;
    } else if (x < rht->data) {
        insert(x, rht->left);
    } else {
        insert(x, rht->right);
    }
}

void BinarySearchTree::deleteNode(int x, Node *&rhs) {
    if (rhs == 0) {
        return;
    }
    if (x < rhs->data) {
        deleteNode(x, rhs->left);
    } else if (x > rhs->data) {
        deleteNode(x, rhs->right);
    } else if (rhs->left != 0 && rhs->right != 0) {
        Node *p = rhs->right;
        while (p->left != 0) {
            p = p->left;
        }
        rhs->data = p->data;
        deleteNode(rhs->data, rhs->right);
    } else {
        Node *clean = rhs;
        rhs = (rhs->left != 0) ? rhs->left : rhs->right;
        delete clean;
        sum--;
    }
}

void BinarySearchTree::deleteEqual(int x) { deleteEqual(x, root); }

void BinarySearchTree::deleteEqual(int x, Node *&rht) {
    deleteNode(x, root);
    if (sum == 0) {
        root = NULL;
    }
}

void BinarySearchTree::find(int x) { find(x, root); }

void BinarySearchTree::find(int x, Node *&rht) {
    if (rht == 0) {
        cout << "N\n";
    } else if (x == rht->data) {
        cout << "Y\n";
    } else if (x < rht->data) {
        find(x, rht->left);
    } else {
        find(x, rht->right);
    }
}

int BinarySearchTree::findMin(int x) {
    int ans = 2147483646;
    int p;
    Node *n = root;

    while (n != 0) {
        if (x < n->data) {
            ans = min((n->data - x), ans);
            n = n->left;
        } else if (x > n->data) {
            ans = min((x - n->data), ans);
            n = n->right;
        } else {
            return 0;
        }
    }

    return ans;
}

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

    int n, order;
    int x;
    BinarySearchTree bst;

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> order >> x;
        switch (order) {
            case 0:
                cout << bst.findMin(x) << '\n';
                break;
            case 1:
                bst.insert(x);
                break;
            case 2:
                bst.deleteEqual(x);
                break;
        }
    }

    return 0;
}

q4x3's solution

/**
 * 二叉搜索树
 **/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

struct node {
    int data;
    node *left, *right;
    node(int dt):data(dt), left(nullptr), right(nullptr) {}
};

void insert(node* &rt, int p) {
    if(rt == nullptr) {
        rt = new node(p);
    } else if(rt->data < p) {
        insert(rt->right, p);
    } else if(rt->data > p) {
        insert(rt->left, p);
    }
}

void del(node* &rt, int key) {
    if(rt->data < key) {
        del(rt->right, key);
        return;
    } else if(rt->data > key) {
        del(rt->left, key);
        return;
    }
    if(rt->left == nullptr && rt->right == nullptr) {
        delete rt;
        rt = nullptr;
    } else if(rt->left && rt->right == nullptr) {
        rt = rt->left;
    } else if(rt->left == nullptr && rt->right) {
        rt = rt->right;
    } else {
        node* tmp = rt->right;
        while(tmp->left) tmp = tmp->left;
        rt->data = tmp->data;
        del(rt->right, rt->data);
    }
}

int min(int x, int y) {
    return x < y ? x : y;
}

int query(node* rt, int x) {
    int ans = 2e9;
    while(rt != nullptr) {
        if(rt->data < x) {
            ans = min(ans, x - rt->data);
            rt = rt->right;
        } else if(rt->data > x) {
            ans = min(ans, rt->data - x);
            rt = rt->left;
        } else return 0;
    }
    return ans;
}

node *root;
int M, op, x;

int main() {
    scanf("%d", &M);
    for(int i = 0;i < M;++ i) {
        scanf("%d%d", &op, &x);
        if(op == 0) {
            printf("%d\n", query(root, x));
        } else if(op == 1) {
            insert(root, x);
        } else {
            del(root, x);
        }
    }
}

victrid's solution

#include <cstdio>
#include <iostream>
using namespace std;
#include <cmath>
template <typename T>
class AVL {
protected:
    struct node {
        node* left;
        node* right;
        int height;
        T value;
    };
    node* data;
    size_t __size;
    node* i_query(node* root, T& to_query) {
        if (root == nullptr)
            return nullptr;
        if (root->value == to_query)
            return root;
        if (root->value > to_query) {
            return i_query(root->left, to_query);
        }
        if (root->value < to_query) {
            return i_query(root->right, to_query);
        }
    }
    void setrootheight(node* root) {
        if (root == nullptr)
            return;
        root->height = max((root->left == nullptr ? 0 : root->left->height), (root->right == nullptr ? 0 : root->right->height)) + 1;
    }

    node* right_rotate(node*& root) {
        node* nl   = root->left;
        root->left = nl->right;
        nl->right  = root;
        root       = nl;
        setrootheight(root->left);
        setrootheight(root->right);
        setrootheight(root);
        return root;
    }

    node* left_rotate(node*& root) {
        node* nr    = root->right;
        root->right = nr->left;
        nr->left    = root;
        root        = nr;
        setrootheight(root->left);
        setrootheight(root->right);
        setrootheight(root);
        return root;
    }

    inline int getfactor(node*& root) {
        if (root == nullptr)
            return 0;
        return (root->left == nullptr ? 0 : root->left->height) - (root->right == nullptr ? 0 : root->right->height);
    }

    int balance(node*& root) {
        if (root == nullptr)
            return 0;
        setrootheight(root->left);
        setrootheight(root->right);
        setrootheight(root);
        while (abs(getfactor(root->left)) > 1) {
            balance(root->left);
            setrootheight(root->left);
            setrootheight(root);
        }
        while (abs(getfactor(root->right)) > 1) {
            balance(root->right);
            setrootheight(root->right);
            setrootheight(root);
        }
        int p = getfactor(root);
        if (abs(p) <= 1)
            return 0;
        if (p > 0) {
            if (getfactor(root->left) == 1) {
                right_rotate(root);
                return 0;
            } else {
                left_rotate(root->left);
                right_rotate(root);
                return 0;
            }
        } else {
            if (getfactor(root->right) == -1) {
                left_rotate(root);
                return 0;
            } else {
                right_rotate(root->right);
                left_rotate(root);
                return 0;
            }
        }
    }

    int insert(node*& root, T& to_insert) {
        if (root == nullptr) {
            root = new node{nullptr, nullptr, 1, to_insert};
            __size++;
            return 0;
        }
        if (root->value < to_insert)
            insert(root->right, to_insert);
        else
            insert(root->left, to_insert);
        balance(root);
        return 0;
    }

    node* erasemin(node*& root) {
        if (root == nullptr)
            return nullptr;
        node* to_erase;
        if (root->left == nullptr) {
            to_erase = root;
            root     = root->right;
        } else {
            return erasemin(root->left);
        }
        balance(root);
        return to_erase;
    }

    int erase(node*& root, T& to_delete) {
        if (root == nullptr)
            return -1;
        if (root->value < to_delete)
            erase(root->right, to_delete);
        else if (root->value > to_delete)
            erase(root->left, to_delete);
        else if (root->value == to_delete) {
            __size--;
            node* rr = root;
            if (root->right == nullptr && root->left == nullptr) {
                root = nullptr;
            } else if (root->right == nullptr) {
                root = root->left;
            } else if (root->left == nullptr) {
                root = root->right;
            } else {
                node*& pp   = root->right;
                node* bl    = root->left;
                root        = erasemin(root->right);
                root->right = pp;
                root->left  = bl;
            }
            delete rr;
        }
        balance(root);
        return 0;
    }

public:
    AVL() : data(nullptr), __size(0){};
    int insert(T dat) {
        if (i_query(data, dat) != nullptr)
            return -1;
        else {
            insert(data, dat);
            return 0;
        }
    }
    int find(T dat) {
        return (i_query(data, dat) != nullptr);
    }
    int erase(T dat) {
        if (i_query(data, dat) == nullptr)
            return -1;
        else {
            erase(data, dat);
            return 0;
        }
    }
    int size() {
        return __size;
    }
};
int main() {
    class tr : public AVL<int> {
    protected:
        node* i_qy(node* root, int& to_query, int& valuemin) {
            if (root == nullptr)
                return nullptr;
            if (root->value == to_query) {
                valuemin = 0;
                return root;
            }
            if (root->value > to_query) {
                if (root->value - to_query < valuemin)
                    valuemin = root->value - to_query;
                return i_qy(root->left, to_query, valuemin);
            }
            if (root->value < to_query) {
                if (to_query - root->value < valuemin)
                    valuemin = to_query - root->value;
                return i_qy(root->right, to_query, valuemin);
            }
            return nullptr;
        }

    public:
        int query(int& val) {
            int valuemin = abs(val - data->value);
            i_qy(data, val, valuemin);
            return valuemin;
        }
    } tree;
    int M, a, b;
    scanf("%d", &M);
    while (M--) {
        scanf("%d%d", &a, &b);
        switch (a) {
        case 1:
            tree.insert(b);
            break;
        case 2:
            tree.erase(b);
            break;
        case 0:
            printf("%d\n", tree.query(b));
            break;
        }
    }
    return 0;
}