时间限制: 1 Sec 内存限制: 128 MB
提交: 18 解决: 9
题目描述
实现一种数据结构，维护以下两个操作：
（1） I x ：加入元素 x ；
（2） M ：输出当前表中相差最小的两个元素的差。
一开始表为空，插入次数不超过 50000 ，插入的数字不超过 220−1 且都为正数，如果要插入的是前面已有的元素，则不处理。
输入
第一行为操作数，以下每行一种操作
输出
对于每个 M 的操作，输出对应的结果，每行一个数。
样例输入
5
I 1
I 10
M
I 6
M
样例输出
9
4
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
int n;
struct node
{
int key;
node *child[];
}bst[],*root,*pos;
queue<node*>mem;
void newnode(node* &r,int key)
{
if(mem.empty())r=pos++;
else r=mem.front(),mem.pop();
r->key=key;
r->child[]=r->child[]=NULL;
}
void insert(node* &r,int key)
{
if(r==NULL)newnode(r,key);
else insert(r->child[r->key<key],key);
}
bool exist(node* &r,int key)
{
if(r==NULL)return false;
if(r->key>key)return exist(r->child[],key);
else return (r->key==key)||exist(r->child[],key);
}
int mmin(node* &r,int key)
{
if(r==NULL)return key;
if(r->key<=key)return mmin(r->child[],key);
else
{
int s=mmin(r->child[],key);
if(s==key)return r->key;
}
}
int mmax(node* &r,int key)
{
if(r==NULL)return key;
if(r->key>=key)return mmax(r->child[],key);
else
{
int s=mmax(r->child[],key);
if(s==key)return r->key;
}
}
int main()
{
root=NULL;
pos=bst;
int i,j,num,ans=;
char s[];
scanf("%d",&n);
for(i=;i<=n;i++)
{
scanf("%s",s);
if(s[]=='I')
{
scanf("%d",&num);
if(i==)
{
insert(root,num);
continue;
}
if(root,exist(root,num))continue;
int a=mmin(root,num),b=mmax(root,num);
if(a==num)a=;if(b==num)b=;
ans=min(ans,min(abs(num-a),abs(num-b)));
insert(root,num);
}
else printf("%d\n",ans);
}
}