开始学习新知识：splay——tree

是个板子题，学习splay可以看博客

https://blog.csdn.net/Clove_unique/article/details/50630280

#include
     
      #include
      
       #include
       
        using namespace std;#define MAXN 1000000int ch[MAXN][2],f[MAXN],size[MAXN],cnt[MAXN],key[MAXN];int sz,root;inline void clear(int x){    ch[x][0]=ch[x][1]=f[x]=size[x]=cnt[x]=key[x]=0;}inline bool get(int x){    return ch[f[x]][1]==x;}inline void update(int x){
   //更新结点x的size    if(x){        size[x]=cnt[x];        if(ch[x][0]) size[x]+=size[ch[x][0]];        if(ch[x][1]) size[x]+=size[ch[x][1]];    }}inline void rotate(int x){
   //一次旋转    //得到x的父亲，爷爷，是不是左子树    int old=f[x],oldf=f[old],whichx=get(x);    ch[old][whichx]=ch[x][whichx^1];    f[ch[old][whichx]]=old;        ch[x][whichx^1]=old;f[old]=x;    f[x]=oldf;    if(oldf) ch[oldf][ch[oldf][1]==old]=x;    update(old);update(x);//不要忘记更新size}inline void splay(int x){    for(int fa;fa=f[x];rotate(x))//再把x翻上来        if(f[fa])//如果fa非根，且x和fa是同一侧，那么先翻转fa，否则先翻转x             rotate((get(x)==get(fa))?fa:x);    root=x;//最后把x设为root    }inline void insert(int x){    if(root==0){
   //插到空树里        sz++;ch[sz][0]=ch[sz][1]=f[sz]=0;        root=sz;size[sz]=cnt[sz]=1;key[sz]=x;        return;    }    int now=root,fa=0;    while(1){
   //不断往下寻找直到找到对应值        if(x==key[now]){            cnt[now]++;update(now);update(fa);            splay(now);break;//把now置顶        }        fa=now;        now=ch[now][key[now]
        
         1    if(cnt[root]>1){cnt[root]--;update(root);return;}    //单个x    if(!ch[root][0] && !ch[root][1]){clear(root);root=0;return;}    //只有左子树或者只有右子树    if(!ch[root][0]){
   //删掉根，右儿子做根        int oldroot=root;root=ch[root][1];f[root]=0;clear(oldroot);return;    }    if(!ch[root][1]){        int oldroot=root;root=ch[root][0];f[root]=0;clear(oldroot);return;    }    //前驱作为根（前驱是没有右儿子的），右子树挂到前驱的右子树，删掉根    else {        int pree=pre(),oldroot=root;        splay(pree);        ch[root][1]=ch[oldroot][1];        f[ch[oldroot][1]]=pree;        clear(oldroot);        update(pree);    }}int main(){    int n,op,x;    scanf("%d",&n);    for(int i=1;i<=n;i++){        scanf("%d%d",&op,&x);        switch(op){            case 1:insert(x);break;            case 2:del(x);break;            case 3:printf("%d\n",find(x));break;            case 4:printf("%d\n",findx(x));break;            case 5:insert(x);printf("%d\n",key[pre()]);del(x);break;            case 6:insert(x);printf("%d\n",key[next()]);del(x);break;        }    }}