题目：
代码(在TLE了无限次之后突然发现在删除操作中将左子树最大的数splay到根之后还可能出现右边子树仍然存在与其相等的数的情况 5555):
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std;
struct node{
int k,s;
node *left,*right;
}*roof;
node *bank=new(node);
int n,ans;
void zag(node*&t){
node *k=t->right;
t->right=k->left;
t->s=t->left->s+t->right->s+1;
k->left=t;
k->s=k->left->s+k->right->s+1;
t=k;
}
void zig(node*&t){
node *k=t->left;
t->left=k->right;
t->s=t->left->s+t->right->s+1;
k->right=t;
k->s=k->left->s+k->right->s+1;
t=k;
}
void Merright(node *t,node*&r){
if(r==NULL){
r=t;
}else{
r->s+=t->s;
r->left=t;
zig(r);
}
}
void Merleft(node *t,node*&l){
if(l==NULL){
l=t;
}else{
l->s+=t->s;
l->right=t;
zag(l);
}
}
void splay(int x,node*&t){
node *l=NULL,*r=NULL,*m=t;
while(m->k!=x&&m!=bank){
if(x<m->k){
if(x<m->left->k&&m->left!=bank)zig(m);
node *u=m->left;
m->s-=u->s;
m->left=bank;
Merright(m,r);
m=u;
}else{
if(x>m->right->k&&m->right!=bank)zag(m);
node *u=m->right;
m->s-=u->s;
m->right=bank;
Merleft(m,l);
m=u;
}
}
if(l){
m->s+=l->s;
node *u=m->left;
m->left=l;
m->left->s+=u->s;
m->left->right=u;
}
if(r){
m->s+=r->s;
r->s+=m->right->s;
node *u=m->right;
m->right=r;
m->right->left=u;
}
t=m;
}
int getmax(node *t){
int rec=-0x7fffffff;
while(t!=bank){
rec=max(rec,t->k);
t=t->right;
}
return rec;
}
void INSERT(int k){
node *t=roof,*T=NULL;
bool flag;
while(t!=bank){
T=t;
t->s++;
if(k<t->k) t=t->left,flag=true
; else t=t->right,flag=false;
}
t=new(node);
t->s=1;
t->left=t->right=bank;
t->k=k;
if(T){
if(flag){
T->left=t;
}else T->right=t;
}else roof=t;
}
void DELETE(int k){
splay(k,roof);
if(roof->left!=bank){
splay(getmax(roof->left),roof->left);
while(roof->left->right!=bank)zag(roof->left);
node *p=roof;
roof->left->s+=roof->right->s;
if(roof->left->right!=bank){
while(1);
}
roof->left->right=roof->right;
roof=roof->left;
delete(p);
}else{
node *p=roof;
roof=roof->right;
delete(p);
}
}
int select(int k,node *t){
while(1){
if(t->left->s==k-1)return t->k;
if(t->left->s>k-1) t=t->left
; else k-=t->left->s,k--,t=t->right;
}
}
int Rank(int k,node *t){
int rec=0;
while(t!=bank){
ans=t->k;
if(k<=t->k) t=t->left
; else rec+=t->left->s,rec++,t=t->right;
}
return rec;
}
int prefix(int k,node *t){
int rec=-0x7fffffff;
while(t!=bank){
if(t->k>=k) t=t->left
; else rec=max(rec,t->k),t=t->right;
}
return rec;
}
int suffix(int k,node *t){
int rec=0x7fffffff;
while(t!=bank){
if(t->k<=k) t=t->right
; else rec=min(rec,t->k),t=t->left;
}
return rec;
}
int main(){
roof=bank->left=bank->right=bank;
bank->s=0;
scanf("%d",&n);
while(n--){
int x,y;
scanf("%d%d",&x,&y);
switch(x){
case 1:
INSERT(y);
splay(y,roof);
break;
case 2:
DELETE(y);
break;
case 3:
printf("%d\n",Rank(y,roof)+1);
splay(ans,roof);
break;
case 4:
printf("%d\n",ans=select(y,roof));
splay(ans,roof);
break;
case 5:
printf("%d\n",ans=prefix(y,roof));
splay(ans,roof);
break;
case 6:
printf("%d\n",ans=suffix(y,roof));
splay(ans,roof);
}
}
return 0;
}
