# 12111: 【原2111】最小差值

### 题目描述

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

## Input Format

0 x, 询问要求的最小值

1 x, 插入元素$$x$$

2 x, 删除元素$$x$$

## Sample Input

5
1 0
1 1
0 2
2 1
0 2


## Sample Output

1
2


## 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);
}

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;
}