[Splay模版1]

输入

第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大的数

细节在代码中：

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cstdlib>
  5 #include<cmath>
  6 #include<cstring>
  7 #include<ctime>
  8 using namespace std;
  9 const int N=200005,INF=1000000001;
 10 struct node
 11 {
 12     node *child[2],*fa;
 13     int x;
 14 }a[N];
 15 node *pos=a,*root;
 16 void newnode(node *&r,int key,node *&fa)
 17 {
 18     r=pos++;
 19     r->child[0]=r->child[1]=NULL;
 20     r->x=key;r->fa=fa;
 21 }
 22 
 23 void insert(node *&r,int key,node *fa)
 24 {
 25     if(r==NULL){
 26         newnode(r,key,fa);
 27         return ;
 28     }
 29     insert(r->child[key>r->x],key,r);
 30 }
 31 node *pre,*nxt;
 32 void rotate(node *&r,bool t)//0left 1right 
 33 {
 34     node *y=r->fa;
 35     y->child[!t]=r->child[t];
 36     if(r->child[t])r->child[t]->fa=y;
 37     if(y->fa)y->fa->child[y->fa->child[1]==y]=r;
 38     r->fa=y->fa;
 39     r->child[t]=y;
 40     y->fa=r;
 41 }
 42 void check(node *r)//输出整个SPLAY 
 43 {
 44     if(r==NULL)return ;
 45     printf("x=%d lchild=%d rchild=%d
",r->x,(r->child[0]==NULL?NULL:r->child[0]->x),r->child[1]==NULL?NULL:r->child[1]->x);
 46     check(r->child[0]);
 47     check(r->child[1]);
 48 }
 49 void getpre(node *r,int key)
 50 {
 51     if(r==NULL)return ;
 52     if(key<=r->x)getpre(r->child[0],key);
 53     else pre=r,getpre(r->child[1],key);
 54 }
 55 void getnext(node *r,int key)
 56 {
 57     if(r==NULL)return ;
 58     if(key>=r->x)getnext(r->child[1],key);
 59     else nxt=r,getnext(r->child[0],key);
 60 }
 61 void getans(node *r,int key)
 62 {
 63     if(r==NULL)return ;
 64     if(key<r->x)getans(r->child[0],key);//注意这里key<r->x不能取等 
 65     else pre=r,getans(r->child[1],key);
 66 }
 67 void splay(node *r,node *g)
 68 {
 69     while(r->fa!=g)
 70     {
 71         if(r->fa->fa==g)rotate(r,r->fa->child[0]==r);
 72         else{
 73             node *y=r->fa;
 74             bool b=y->fa->child[0]==y;
 75             if(y->child[b]==r)rotate(r,!b);
 76             else rotate(y,b);
 77             rotate(r,b);
 78         } 
 79     }
 80     if(g==NULL)root=r;
 81 }
 82 
 83 void work(int l,int r)
 84 {
 85     getpre(root,l);getnext(root,r);
 86     splay(pre,NULL);
 87     splay(nxt,pre);
 88     root->child[1]->child[0]=NULL;
 89 }
 90 void haha()//**********插入INF 和 -INF 避免找不到小于l和大于r的数************* 
 91 {
 92     insert(root,INF,NULL);insert(root,-INF,NULL);
 93     return ;
 94 }
 95 int main()
 96 {
 97     haha();
 98     int n,x,y;char ch;
 99     scanf("%d",&n);
100     while(n--)
101     {
102         scanf("
%c%d",&ch,&x);
103         if(ch=='I'){
104             insert(root,x,NULL);
105         }
106         if(ch=='Q'){
107             getans(root,x);
108             printf("%d
",pre->x);
109         }
110         if(ch=='D'){
111             scanf("%d",&y);
112             work(x,y);
113         }
114     }
115 }