题目描述
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
- 插入x数
- 删除x数(若有多个相同的数，因只删除一个)
- 查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数，因输出最小的排名)
- 查询排名为x的数
- 求x的前驱(前驱定义为小于x，且最大的数)
- 求x的后继(后继定义为大于x，且最小的数)
输入输出格式
输入格式：
第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1≤opt≤6)
输出格式：
对于操作3,4,5,6每行输出一个数，表示对应答案
输入输出样例
输入样例：
输出样例：
Splay 解析尚未完成 参见yyb dalao的博客
丑陋的代码送上（yyb大佬的代码比我的漂亮多了）：
#ifndef SPLAY_TREE_HPP
#define SPLAY_TREE_HPP
#include<bits/stdc++.h>
using namespace std;
namespace Splay_tree
{
template<typename T>
struct splay_node
{
T value;
int size;
int cnt;
bool reverse;
splay_node *father;
splay_node *son[];
splay_node(){}
splay_node(T v, splay_node *f=NULL)
:value(v),cnt()
{
father=f;
size=;
son[]=son[]=NULL;
}
}; template<typename T, typename C=less<T> >
class Splay
{
private:
typedef splay_node<T> node;
node *root;
C small_to;
bool big_to(T x, T y){return small_to(y,x);}
bool equal_to(T x, T y){return !(small_to(x,y)||big_to(x,y));} inline bool son(node *f, node *s)
{
return f->son[]==s;
}
inline void rotate(node *t)
{
node *f = t->father;
node *g = f->father;
bool a = son(f, t), b = !a;
f->son[a] = t->son[b];
if (t->son[b] != NULL)
t->son[b]->father = f;
t->son[b] = f;
f->father = t;
t->father = g;
if (g != NULL)
g->son[son(g, f)] = t;
else
root = t;
update(f);
update(t);
} inline void splay(node *t, node *p)
{
while (t->father != p)
{
node *f = t->father;
node *g = f->father;
if (g == p)
rotate(t);
else
{
if (son(g, f) ^ son(f, t)) rotate(t), rotate(t);
else rotate(f), rotate(t);
}
}
update(t);
} inline T k_th(int k, node *f)
{
int tmp;
node *t=root;
while()
{
int tmp=size(t->son[])+t->cnt;
int sze=tmp-t->cnt;
if(k<=tmp&&sze<k) break;
else if(k<=sze) t=t->son[];
else k-=tmp,t=t->son[];
}
T ans=t->value;
return ans;
} inline node* insert(T val, node *t)
{
int b=big_to(val,t->value);
if(equal_to(val,t->value))
{
t->cnt++;
update(t);
return t;
}
if(t->son[b]==NULL)
{
t->son[b]=new node(val,t);
update(t->son[b]);
update(t);
return t->son[b];
}
else
{
node *ans=insert(val,t->son[b]);
update(t);
return ans;
}
} public:
Splay()
{
root=NULL;
} inline void insert(T val)
{
if (root == NULL)
{
root = new node(val, NULL);
update(root);
return;
}
else
{
node *t = insert(val,root);
splay(t,NULL);
}
} inline void erase(T val)
{
node *t = root;
while(t)
{
if (equal_to(t->value,val))
break;
t = t->son[big_to(val,t->value)];
}
if (t != NULL)
{
splay(t, NULL);
if(t->cnt>)
{
t->cnt--;
update(t);
return;
}
if (t->son[] == NULL)
{
root = t->son[];
if (root != NULL)
{
root->father = NULL;
update(root);
}
}
else
{
node *p = t->son[];
while (p->son[] != NULL)
p = p->son[];
splay(p, t); root = p;
root->father = NULL;
p->son[] = t->son[];
update(p);
if (p->son[] != NULL)
p->son[]->father = p;
}
}
} inline T pre(T val)
{
T ans=pre_ptr(val)->value;
return ans;
} inline T suc(T val)
{
node *x = root;
insert(val);
node *t=root->son[];
if(t==NULL) return T(NULL);
while(t->son[]!=NULL) t=t->son[];
erase(val);
T ans=t->value;
return ans;
} inline T max_value()
{
node *t=root;
while(t->son[]!=NULL) t=t->son[];
return t->value;
} inline T min_value()
{
node *t=root;
while(t->son[]!=NULL) t=t->son[];
return t->value;
} inline T k_th(int k)
{
return k_th(k,NULL);
} inline int rank(T val)
{
node *t=root;
while(!equal_to(t->value, val))
t=t->son[big_to(val,t->value)];
splay(t,NULL);
return size(t->son[])+;
} inline void print()
{
print(root);
puts("");
} private: inline node* pre_ptr(T val)
{
insert(val);
node *t=root->son[];
if(t==NULL) return NULL;
while(t->son[]!=NULL) t=t->son[];
erase(val);
return t;
} inline void print(node *t)
{
if(t==NULL) return;
print(t->son[]);
printf("%d ",t->value);
print(t->son[]);
} inline int size(node *t)
{
return t == NULL ? : t->size;
} inline void update(node *t)
{
t->size = t->cnt;
t->size += size(t->son[]);
t->size += size(t->son[]);
}
};
}
#endif int main()
{
using namespace Splay_tree;
int n;
Splay<int> tree;
scanf("%d",&n);
for(int i=;i<=n;i++)
{
int ops;
int x;
scanf("%d%d",&ops,&x);
switch(ops)
{
case :
tree.insert(x);
break;
case :
tree.erase(x);
break;
case :
{
int t=tree.rank(x);
printf("%d\n",t);
break;
}
case :
{
int y=tree.k_th(x);
printf("%d\n",y);
break;
}
case :
printf("%d\n",tree.pre(x));
break;
case :
int t=tree.suc(x);
printf("%d\n",t);
break;
}
}
}