输入
第1行：1个正整数n，表示操作数量，100≤n≤200,000
第2..n+1行：可能包含下面3种规则：
1个字母'I'，紧接着1个数字k，表示插入一个数字k到树中，1≤k≤1,000,000,000，保证每个k都不相同
1个字母'Q'，紧接着1个数字k。表示询问树中不超过k的最大数字
1个字母'D'，紧接着2个数字a,b，表示删除树中在区间[a,b]的数。
输出
若干行：每行1个整数，表示针对询问的回答，保证一定有合法的解
样例输入
6 I 1 I 2 I 3 Q 4 D 2 2 Q 2
样例输出
3 1
Splay模版
注意在平衡树中要加入INF 和 -INF 避免找不到比L小的数和比R大的数
细节在代码中：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<ctime>
using namespace std;
const int N=,INF=;
struct node
{
node *child[],*fa;
int x;
}a[N];
node *pos=a,*root;
void newnode(node *&r,int key,node *&fa)
{
r=pos++;
r->child[]=r->child[]=NULL;
r->x=key;r->fa=fa;
} void insert(node *&r,int key,node *fa)
{
if(r==NULL){
newnode(r,key,fa);
return ;
}
insert(r->child[key>r->x],key,r);
}
node *pre,*nxt;
void rotate(node *&r,bool t)//0left 1right
{
node *y=r->fa;
y->child[!t]=r->child[t];
if(r->child[t])r->child[t]->fa=y;
if(y->fa)y->fa->child[y->fa->child[]==y]=r;
r->fa=y->fa;
r->child[t]=y;
y->fa=r;
}
void check(node *r)//输出整个SPLAY
{
if(r==NULL)return ;
printf("x=%d lchild=%d rchild=%d\n",r->x,(r->child[]==NULL?NULL:r->child[]->x),r->child[]==NULL?NULL:r->child[]->x);
check(r->child[]);
check(r->child[]);
}
void getpre(node *r,int key)
{
if(r==NULL)return ;
if(key<=r->x)getpre(r->child[],key);
else pre=r,getpre(r->child[],key);
}
void getnext(node *r,int key)
{
if(r==NULL)return ;
if(key>=r->x)getnext(r->child[],key);
else nxt=r,getnext(r->child[],key);
}
void getans(node *r,int key)
{
if(r==NULL)return ;
if(key<r->x)getans(r->child[],key);//注意这里key<r->x不能取等
else pre=r,getans(r->child[],key);
}
void splay(node *r,node *g)
{
while(r->fa!=g)
{
if(r->fa->fa==g)rotate(r,r->fa->child[]==r);
else{
node *y=r->fa;
bool b=y->fa->child[]==y;
if(y->child[b]==r)rotate(r,!b);
else rotate(y,b);
rotate(r,b);
}
}
if(g==NULL)root=r;
} void work(int l,int r)
{
getpre(root,l);getnext(root,r);
splay(pre,NULL);
splay(nxt,pre);
root->child[]->child[]=NULL;
}
void haha()//**********插入INF 和 -INF 避免找不到小于l和大于r的数*************
{
insert(root,INF,NULL);insert(root,-INF,NULL);
return ;
}
int main()
{
haha();
int n,x,y;char ch;
scanf("%d",&n);
while(n--)
{
scanf("\n%c%d",&ch,&x);
if(ch=='I'){
insert(root,x,NULL);
}
if(ch=='Q'){
getans(root,x);
printf("%d\n",pre->x);
}
if(ch=='D'){
scanf("%d",&y);
work(x,y);
}
}
}