//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 的格式要求是 "插入 [该代码片段的中文名]"

{
    "二逼平衡树": {
        "prefix": "acm-2.6树套树(有注释",
        "body": [
            "#pragma GCC optimize(2)",
            "#pragma GCC optimize(3,\"Ofast\",\"inline\")",
            "#include<algorithm>",
            "#include<cstring>",
            "#include<cstdio>",
            "#define mid (L+R>>1)",
            "#define Re register int",
            "#define pl tree[p].lp",
            "#define pr tree[p].rp",
            "#define F(i,a,b) for(Re i=a;i<=b;++i)",
            "#define lo(o) lower_bound(b+1,b+m+1,o)-b",
            "using namespace std;",
            "const int N=1e5+3,inf=2147483647;",
            "int x,y,z,n,m,T,t,fu,cnt,tl,tr,a[N],b[N],pt[N],C[N],opt[N],ptl[20],ptr[20]; ",
            "struct QAQ{int g,lp,rp;}tree[N*250];",
            "struct O_O{int l,r,k;}Q[N];",
            "struct T_T{int i,x;}c[N];",
            "inline void in(Re &x){",
            "    x=fu=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 int ask_kth(Re L,Re R,Re k){",
            "    if(L==R)return b[R];",
            "    Re tmp=0;",
            "    F(i,1,tl)tmp-=tree[tree[ptl[i]].lp].g;",
            "    F(i,1,tr)tmp+=tree[tree[ptr[i]].lp].g;",
            "    if(tmp>=k){",
            "    \tF(i,1,tl)ptl[i]=tree[ptl[i]].lp;",
            "    \tF(i,1,tr)ptr[i]=tree[ptr[i]].lp;",
            "    \treturn ask_kth(L,mid,k);",
            "    }",
            "    else{",
            "    \tF(i,1,tl)ptl[i]=tree[ptl[i]].rp;",
            "    \tF(i,1,tr)ptr[i]=tree[ptr[i]].rp;",
            "    \treturn ask_kth(mid+1,R,k-tmp);",
            "    }",
            "}",
            "inline int ask_kth_pre(Re L,Re R,Re k){",
            "    tl=tr=0;",
            "    for(Re i=L-1;i;i-=i&-i)ptl[++tl]=pt[i];",
            "    for(Re i=R;i;i-=i&-i)ptr[++tr]=pt[i];",
            "    return ask_kth(1,m,k);",
            "}",
            "inline void add(Re &p,Re L,Re R,Re w,Re v){",
            "    if(!p)p=++cnt;tree[p].g+=v;",
            "    if(L==R)return;",
            "    if(w<=mid)add(pl,L,mid,w,v);",
            "    else add(pr,mid+1,R,w,v);",
            "}",
            "inline void add_pre(Re x,Re v){",
            "    Re w=lo(a[x]);",
            "    for(Re i=x;i<=n;i+=i&-i)add(pt[i],1,m,w,v);",
            "}",
            "inline int ask_level(Re p,Re L,Re R,Re x){",
            "\tif(L==R)return tree[p].g; ",
            "\tif(x<=mid)return ask_level(pl,L,mid,x);",
            "\telse return tree[pl].g+ask_level(pr,mid+1,R,x);",
            "}",
            "inline int ask_level_pre(Re L,Re R,Re w){",
            "\tRe ans=0;",
            "    for(Re i=R;i;i-=i&-i)ans+=ask_level(pt[i],1,m,w);",
            "    for(Re i=L-1;i;i-=i&-i)ans-=ask_level(pt[i],1,m,w);",
            "    return ans;",
            "}",
            "int main(){",
            "//\tprintf(\"%lf\\n\",(sizeof(tree))/1024.0/1024.0);",
            "//\tprintf(\"%lf\\n\",(sizeof(tree)+sizeof(Q)+sizeof(c)+sizeof(a)+sizeof(b)+sizeof(pt)+sizeof(C))/1024.0/1024.0);",
            "\tin(n),in(T),m=n;",
            "    F(i,1,n)in(a[i]),b[i]=a[i];",
            "    F(i,1,T){",
            "    \tin(opt[i]);",
            "    \tif(opt[i]==3)in(c[i].i),in(c[i].x),b[++m]=c[i].x;",
            "    \telse{",
            "    \t\tin(Q[i].l),in(Q[i].r),in(Q[i].k);",
            "    \t\tif(opt[i]!=2)b[++m]=Q[i].k;",
            "\t\t}",
            "    }",
            "    sort(b+1,b+m+1);",
            "    m=unique(b+1,b+m+1)-b-1;",
            "    F(i,1,n)add_pre(i,1);",
            "    F(i,1,T){",
            "    \tif(opt[i]==1)",
            "    \t\tQ[i].k=lo(Q[i].k),",
            "\t\t\tprintf(\"%d\\n\",ask_level_pre(Q[i].l,Q[i].r,Q[i].k-1)+1);",
            "",
            "    \tif(opt[i]==2)",
            "    \t\tprintf(\"%d\\n\",ask_kth_pre(Q[i].l,Q[i].r,Q[i].k));",
            "",
            "\t\tif(opt[i]==3)",
            "\t\t\tadd_pre(c[i].i,-1),a[c[i].i]=c[i].x,add_pre(c[i].i,1);",
            "",
            "\t\tif(opt[i]==4){",
            "\t\t}",
            "",
            "\t\tif(opt[i]==5){",
            "\t\t}",
            "    }",
            "}",
            ""
        ],
        "description": "插入 二逼平衡树"
    }
}