Splay 템 플 릿 / 학습 (업데이트 대기)

http://hihocoder.com/contest/hiho104 hiho 104 를 예 로 들 어 hiho 의 설명 을 보고 이 물건 을 썼 습 니 다. 먼저 이해 하기 쉬 운 템 플 릿 을 만 들 었 습 니 다.

#include
#include
#include
using namespace std;
typedef long long LL;
typedef set<int>::iterator sit;
const LL mod=1e9+7;
const double eps=1e-9;
const int INF=0x3f3f3f3f;
struct Stree{//       0
    int fa;
    int val;
    int l,r;
    int siz;
}sp[200010];
int root,cnt;

void pushup(int rt){
    sp[rt].siz=sp[sp[rt].l].siz+sp[sp[rt].r].siz+1;
}
void rro(int rt){
    int fa=sp[rt].fa;
    int rs=sp[rt].r;
    int gf=sp[fa].fa;
    sp[fa].l=rs;
    sp[rs].fa=fa;
    if(gf){
        if(sp[gf].l==fa)sp[gf].l=rt;
        else sp[gf].r=rt;
    }else root=rt;
    sp[rt].fa=gf;
    sp[rt].r=fa;
    sp[fa].fa=rt;
    pushup(fa);pushup(rt);
}
void lro(int rt){
    int fa=sp[rt].fa;
    int ls=sp[rt].l;
    int gf=sp[fa].fa;
    sp[fa].r=ls;
    sp[ls].fa=fa;
    if(gf){
        if(sp[gf].l==fa)sp[gf].l=rt;
        else sp[gf].r=rt;
    }else root=rt;
    sp[rt].fa=gf;
    sp[rt].l=fa;
    sp[fa].fa=rt;
    pushup(fa);pushup(rt);
}
void splay(int x,int y){//    x     y     
    while(sp[x].fa!=y){
        int fa=sp[x].fa;
        if(sp[fa].fa==y){
            if(sp[fa].l==x)rro(x);
            else lro(x);
        }
        else {
            int gf=sp[fa].fa;
            if(sp[fa].l==x&&sp[gf].l==fa){rro(fa);rro(x);}
            else if(sp[fa].r==x&&sp[gf].r==fa){lro(fa);lro(x);}
            else if(sp[fa].r==x&&sp[gf].l==fa){lro(x);rro(x);}
            else {rro(x);lro(x);}
        }
    }
}
void ist(int &k,int x,int fa){
    if(!k){
        k=++cnt;
        sp[k].val=x;
        sp[k].fa=fa;
        sp[k].siz=1;
        splay(k,0);
        return ;
    }
    if(xelse ist(sp[k].r,x,k);
}
int pre,nxt;
void fdpre(int rt,int x){//         x  ，    pre 
    if(!rt)return ;
    //printf("%d %d
",rt,sp[rt].val);
    if(sp[rt].val==x){pre=rt;return ;}
    if(sp[rt].valelse {fdpre(sp[rt].l,x);}
}
void fdnxt(int rt,int x){//         x  ，    nxt 
    if(!rt)return ;
    if(sp[rt].val==x){nxt=rt;return ;}
    else if(sp[rt].val>x){nxt=rt;fdnxt(sp[rt].l,x);}
    else {fdnxt(sp[rt].r,x);}
}
void del(int l,int r){//    [l,r]
    fdpre(root,l-1);fdnxt(root,r+1);
    splay(pre,0);splay(nxt,pre);
    sp[nxt].l=0;
    pushup(nxt);pushup(pre);
}
void init(){
    cnt=0;root=0;
    ist(root,-INF,0);
    ist(root,INF,0);
}
void print(int rt){
    if(!rt)return ;
    print(sp[rt].l);
    printf("%d %d %d %d
",rt,sp[rt].val,sp[rt].l,sp[rt].r);
    print(sp[rt].r);
}
char op[2];
int main(void)
{
    int n,k,a,b;
    while(~scanf("%d",&n)){
        init();
        while(n--){
            scanf("%s",op);
            if(op[0]=='I'){
                scanf("%d",&k);
                ist(root,k,0);
                //print(root);
            }
            else if(op[0]=='Q'){
                scanf("%d",&k);
                fdpre(root,k);
                printf("%d
",sp[pre].val);
                splay(pre,0);
            }
            else {
                scanf("%d%d",&a,&b);
                del(a,b);
            }
            //for(int i=1;i<=7;i++)printf("%d %d %d %d
",i,sp[i].val,sp[i].l,sp[i].r);
        }
    }
    return 0;
}

역시 너무 길 어 보 였 어 요. 사내 들 의 쓰 는 법 을 보고 다시 배 워 서 다시 누 를 생각 이에 요.https://blog.csdn.net/qq_30974369 / article / details / 77587168 이 큰 놈 의 설명 updated 를 보 세 요. 운영 효율 에 있어 서 아무런 차이 가 없습니다. 주로 rotate 함 수 를 고 친 다음 에 아래 함 수 를 고 칠 때 많은 것 을 생략 할 수 있 습 니 다.

#include
#include
#include
using namespace std;
typedef long long LL;
typedef set<int>::iterator sit;
const LL mod=1e9+7;
const double eps=1e-9;
const int INF=0x3f3f3f3f;
struct Stree{//       0
    int fa,ch[2],val;
    int siz;
}sp[200010];
int root,cnt;// ，    
void pushup(int rt){
    sp[rt].siz=sp[sp[rt].ch[0]].siz+sp[sp[rt].ch[1]].siz+1;
}
void ro(int rt){
    int fa=sp[rt].fa;
    int gf=sp[fa].fa;
    int sid=sp[fa].ch[1]==rt;
    sp[sp[gf].ch[sp[gf].ch[1]==fa]=rt].fa=gf;
    sp[sp[fa].ch[sid]=sp[rt].ch[sid^1]].fa=fa;
    sp[sp[rt].ch[sid^1]=fa].fa=rt;
    if(!gf)root=rt;
    pushup(fa);pushup(rt);
}
void splay(int x,int y){//    x     y     
    while(sp[x].fa!=y){
        int fa=sp[x].fa;
        int gf=sp[fa].fa;
        if(gf!=y){
            if((sp[gf].ch[1]==fa)^(sp[fa].ch[1]==x))ro(x);
            else ro(fa);
        }
        ro(x);
    }
}
void ist(int &k,int x,int fa){
    if(!k){
        k=++cnt;
        sp[k].val=x;sp[k].fa=fa;
        sp[k].siz=1;splay(k,0);
        return ;
    }
    if(x0],x,k);
    else ist(sp[k].ch[1],x,k);
}
int pre,nxt;
void fdpre(int rt,int x){//         x  ，    pre 
    if(!rt)return ;
    //printf("%d %d
",rt,sp[rt].val);
    if(sp[rt].val==x){pre=rt;return ;}
    if(sp[rt].val1],x);}
    else {fdpre(sp[rt].ch[0],x);}
}
void fdnxt(int rt,int x){//         x  ，    nxt 
    if(!rt)return ;
    if(sp[rt].val==x){nxt=rt;return ;}
    else if(sp[rt].val>x){nxt=rt;fdnxt(sp[rt].ch[0],x);}
    else {fdnxt(sp[rt].ch[1],x);}
}
void del(int l,int r){//    [l,r]
    fdpre(root,l-1);fdnxt(root,r+1);
    splay(pre,0);splay(nxt,pre);
    sp[nxt].ch[0]=0;
    pushup(nxt);pushup(pre);
}
void init(){
    cnt=0;root=0;
    ist(root,-INF,0);
    ist(root,INF,0);
}
void print(int rt){
    if(!rt)return ;
    print(sp[rt].ch[0]);
    printf("%d %d %d %d
",rt,sp[rt].val,sp[rt].ch[0],sp[rt].ch[1]);
    print(sp[rt].ch[1]);
}
char op[2];
int main(void)
{
    int n,k,a,b;
    while(~scanf("%d",&n)){
        init();
        while(n--){
            scanf("%s",op);
            if(op[0]=='I'){
                scanf("%d",&k);
                ist(root,k,0);
                //print(root);
            }
            else if(op[0]=='Q'){
                scanf("%d",&k);
                fdpre(root,k);
                printf("%d
",sp[pre].val);
                splay(pre,0);
            }
            else {
                scanf("%d%d",&a,&b);
                del(a,b);
            }
//          printf("%d
",root);
//          for(int i=1;i<=7;i++)printf("%d %d %d %d
",i,sp[i].val,sp[i].ch[0],sp[i].ch[1]);
        }
    }
    return 0;
}

다음은 업데이트 용법...구 덩이 를 파 서 천천히 메 워 라