Splay平衡树先插入再去查询
C++ 代码
#include <bits/stdc++.h>
using namespace std;
int num[100010];
inline int read()
{
int num = 0; char c = getchar(), up = c;
while (c < '0' || c>'9') up = c, c = getchar();
while (c >= '0' && c <= '9') num = (num << 1) + (num << 3) + (c ^ '0'), c = getchar();
return up == '-' ? -num : num;
}
const int N = 500010;
int root = 0, tot = 0;
struct Node {
int ch[2], cnt, father, son_size, val, wei;
}tree[N];
void push_up(int node)
{
tree[node].son_size = tree[tree[node].ch[0]].son_size + tree[tree[node].ch[1]].son_size + tree[node].cnt;
}
void rotate(int x)//旋转
{
int y = tree[x].father, z = tree[y].father, k = tree[y].ch[1] == x;
tree[z].ch[tree[z].ch[1] == y] = x;
tree[x].father = z;
tree[y].ch[k] = tree[x].ch[k ^ 1];
tree[tree[x].ch[k ^ 1]].father = y;
tree[x].ch[k ^ 1] = y; tree[y].father = x;
push_up(y), push_up(x);
}
void Spaly(int x, int goal)//Splay
{
while (tree[x].father != goal) {
int y = tree[x].father, z = tree[y].father;
if (z != goal) {
(tree[y].ch[0] == x) ^ (tree[z].ch[0] == y) ? rotate(x) : rotate(y);
}
rotate(x);
}
if (goal == 0) {
root = x;
}
}
void insert(int v, int wei)//插入与下标值
{
int x = root, dad = 0;
while (x && tree[x].val != v) {
dad = x;
x = tree[x].ch[v > tree[x].val];
}
if (x) {
tree[x].cnt++;
}
else {
x = ++tot;
if (dad) {
tree[dad].ch[v > tree[dad].val] = x;
}
tree[tot].wei = wei;
tree[tot].ch[0] = 0;
tree[tot].ch[1] = 0;
tree[tot].father = dad; tree[tot].val = v;
tree[tot].cnt = 1, tree[tot].son_size = 1;
}
Spaly(x, 0);
}
void Find(int v)
{
int x = root;
if (!x) {
return;
}
while (tree[x].ch[v > tree[x].val] && v != tree[x].val) {
x = tree[x].ch[v > tree[x].val];
}
Spaly(x, 0);
}
int Pre_Net(int v, int op)//寻找前驱与后继op==0是寻找前驱,op==2是寻找后继
{
Find(v);
int x = root;
if ((tree[x].val > v && op) || (tree[x].val < v && !op)) {
return x;
}
x = tree[x].ch[op];
while (tree[x].ch[op ^ 1]) {
x = tree[x].ch[op ^ 1];
}
return x;
}
int main()
{
int n;
insert(INT_MIN, INT_MIN), insert(INT_MAX, INT_MAX);//插入最大与最小值
scanf("%d%d", &n, &num[1]);
insert(num[1], 1);//
for (int i = 2; i <= n; i++) {
num[i] = read();
insert(num[i], i);
int pre = tree[Pre_Net(num[i], 0)].val;
int nxt = tree[Pre_Net(num[i], 1)].val;
if (abs(pre - num[i]) < abs(nxt - num[i])) {
cout << abs(pre - num[i]) << " " << tree[Pre_Net(num[i], 0)].wei << endl;
}
else if (abs(pre - num[i]) > abs(nxt - num[i])) {
cout << abs(nxt - num[i]) << " " << tree[Pre_Net(num[i], 1)].wei << endl;
}
else {
cout << abs(pre - num[i]) << " ";
if (pre < nxt) {
cout << tree[Pre_Net(num[i], 0)].wei << endl;
}
else {
cout << tree[Pre_Net(num[i], 1)].wei << endl;
}
}
}
return 0;
}