//Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and 
// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the 
// same ids are connected.
// prefix 的格式要求是 acm-[一级标题编号].[二级标题编号][该代码片段的英文简称]
// description 的格式要求是 "插入 [该代码片段的中文名]"

{
    "Splay  (有注释)": {
        "prefix": "acm-2.7普通平衡树",
        "body": [
            "//#pragma GCC optimize(3,\"Ofast\",\"inline\")",
            "//#pragma GCC optimize(2)",
            "#include<algorithm>",
            "#include<cstdio>",
            "#define Re register int",
            "#define pl tr[p].ps[0]",
            "#define pr tr[p].ps[1]",
            "#define pf tr[p].fa ",
            "#define pv tr[p].v",
            "using namespace std;",
            "const int N=1e5+5,inf=2e9;",
            "int T,a,b,n,o,root;",
            "struct Splay{int v,fa,ps[2],cnt,size;}tr[N];",
            "inline void in(Re &x){",
            "    int fu=0;x=0;char c=getchar();",
            "    while(c<'0'||c>'9')fu|=c=='-',c=getchar();",
            "    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();",
            "    x=fu?-x:x;",
            "}",
            "inline void pushup(Re p){if(!p)return;/*�������Ҫ���ж�return����������*/tr[p].size=tr[p].cnt+tr[pl].size+tr[pr].size;}",
            "inline void connect(Re p,Re f,Re o){tr[tr[p].fa=f].ps[o]=p;}",
            "inline int which(Re p){return tr[pf].ps[1]==p;}",
            "inline void rotate(Re p){",
            "\tRe y=pf,ys=which(p);",
            "\tRe R=tr[y].fa,Rs=which(y);",
            "\tRe B=tr[p].ps[ys^1];",
            "\tconnect(B,y,ys),connect(y,p,ys^1),connect(p,R,Rs);",
            "\tpushup(y),pushup(p);",
            "}",
            "inline void Splay(Re p){",
            "\tfor(Re fa;fa=pf;rotate(p))",
            "\t\tif(tr[fa].fa)rotate(which(p)==which(fa)?fa:p);",
            "\troot=p;",
            "}",
            "inline void New(Re x,Re fa){",
            "\ttr[++o].v=x,tr[o].fa=fa,tr[o].cnt=tr[o].size=1;",
            "\tif(fa)tr[fa].ps[tr[fa].v<x]=o;",
            "}",
            "inline void insert(Re x){",
            "\tif(!root){New(x,0);root=o;return;}",
            "\tint p=root,fa=0;",
            "\twhile(1){",
            "\t\tif(x==pv){++tr[p].cnt,pushup(p),pushup(fa),Splay(p);break;}",
            "\t\tfa=p,p=tr[p].ps[pv<x];",
            "\t\tif(!p){New(x,fa),pushup(fa),Splay(o);break;}",
            "\t}",
            "}",
            "inline int ask_level(Re p,Re x){",
            "//printf(\"p: %d\\n\",p);exit(0);",
            "\tif(x==pv){Re ans=tr[pl].size+1;Splay(p);return ans;}",
            "\telse return x<pv?ask_level(pl,x):tr[p].cnt+tr[pl].size+ask_level(pr,x);",
            "}",
            "inline int ask_v(Re p,Re x){",
            "\tif(x<=tr[pl].size)return ask_v(pl,x);",
            "\telse{",
            "\t\tRe tmp=tr[pl].size+tr[p].cnt;",
            "\t\treturn x<=tmp?pv:ask_v(pr,x-tmp);",
            "\t}",
            "}",
            "inline int ask_nex_p(Re p){p=pr;while(pl)p=pl;return p;}",
            "inline int ask_pri_p(Re p){p=pl;while(pr)p=pr;return p;}",
            "inline void del(Re x){",
            "\task_level(root,x);Re p=root;",
            "\tif(tr[p].cnt>1){--tr[p].cnt,--tr[p].size;return;}",
            "\tif(!pl&&!pr){root=0;return;}",
            "\tif(!pl||!pr){tr[root=pl+pr].fa=0;return;}",
            "\tSplay(ask_pri_p(root));",
            "\ttr[root].ps[1]=pr,tr[pr].fa=root;",
            "\tpushup(root);",
            "}",
            "int main(){",
            "\tin(T);",
            "\twhile(T--){",
            "\t\tin(a),in(b);",
            "\t\tif(a==1)insert(b);",
            "\t\tif(a==2)del(b);",
            "\t\tif(a==3)printf(\"%d\\n\",ask_level(root,b));",
            "\t\tif(a==4)printf(\"%d\\n\",ask_v(root,b));",
            "\t\tif(a==5)insert(b),printf(\"%d\\n\",tr[ask_pri_p(root)].v),del(b);",
            "\t\tif(a==6)insert(b),printf(\"%d\\n\",tr[ask_nex_p(root)].v),del(b);",
            "\t}",
            "}",
            ""
        ],
        "description": "插入 Splay  (有注释)"
    }
}