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

{
    "树套树-单修权值，区间第k小": {
        "prefix": "acm-2.6pl",
        "body": [
            "#include<algorithm>",
            "#include<cstring>",
            "#include<cstdio>",
            "#define LL long long",
            "#define Re register int",
            "using namespace std;",
            "const int N=1e5+3;",
            "int n,m,T,b[N<<1],A[N];char op[N];",
            "struct QWQ{int x,y,k;}Q[N];",
            "inline void in(Re &x){",
            "    int f=0;x=0;char c=getchar();",
            "    while(c<'0'||c>'9')f|=c=='-',c=getchar();",
            "    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();",
            "    x=f?-x:x;",
            "}",
            "int t1,t2,pt[N],ptl[20],ptr[20];",
            "struct President_Tree{",
            "    #define pl (tr[p].lp)",
            "    #define pr (tr[p].rp)",
            "    #define mid ((L+R)>>1)",
            "    int O;",
            "    struct QAQ{int S,lp,rp;}tr[(N<<1)*200];",
            "    inline void change(Re &p,Re L,Re R,Re x,Re v){",
            "        if(!p)p=++O;tr[p].S+=v;",
            "        if(L==R)return;",
            "        if(x<=mid)change(pl,L,mid,x,v);",
            "        else change(pr,mid+1,R,x,v);",
            "    }",
            "    inline int ask(Re p,Re L,Re R,Re K){",
            "        if(L==R)return L;",
            "        Re tmp=0;",
            "        for(Re i=1;i<=t1;++i)tmp-=tr[tr[ptl[i]].lp].S;",
            "        for(Re i=1;i<=t2;++i)tmp+=tr[tr[ptr[i]].lp].S;",
            "        if(K<=tmp){",
            "            for(Re i=1;i<=t1;++i)ptl[i]=tr[ptl[i]].lp;",
            "            for(Re i=1;i<=t2;++i)ptr[i]=tr[ptr[i]].lp;",
            "            return ask(pl,L,mid,K);",
            "        }",
            "        else{",
            "            for(Re i=1;i<=t1;++i)ptl[i]=tr[ptl[i]].rp;",
            "            for(Re i=1;i<=t2;++i)ptr[i]=tr[ptr[i]].rp;",
            "            return ask(pr,mid+1,R,K-tmp);",
            "        }",
            "    }",
            "}SG;",
            "struct BIT{",
            "    inline void add(Re x,Re v){",
            "        for(Re i=x;i<=n;i+=i&-i)SG.change(pt[i],1,m,A[x],v);",
            "    }",
            "    inline int ask(Re L,Re R,Re k){",
            "        t1=t2=0;",
            "        for(Re i=L-1;i;i-=i&-i)ptl[++t1]=pt[i];",
            "        for(Re i=R;i;i-=i&-i)ptr[++t2]=pt[i];",
            "        return SG.ask(1,1,m,k);",
            "    }",
            "}TR;",
            "int main(){",
            "    in(n),in(T),m=n;",
            "    for(Re i=1;i<=n;++i)in(A[i]),b[i]=A[i];",
            "    for(Re i=1;i<=T;++i){",
            "        scanf(\" %c\",&op[i]),in(Q[i].x),in(Q[i].y);",
            "        if(op[i]=='Q')in(Q[i].k);",
            "        else b[++m]=Q[i].y;",
            "    }",
            "    sort(b+1,b+m+1),m=unique(b+1,b+m+1)-b-1;",
            "    for(Re i=1;i<=n;++i)A[i]=lower_bound(b+1,b+m+1,A[i])-b;",
            "    for(Re i=1;i<=T;++i)if(op[i]=='C')Q[i].y=lower_bound(b+1,b+m+1,Q[i].y)-b;",
            "    for(Re i=1;i<=n;++i)TR.add(i,1);",
            "    for(Re i=1;i<=T;++i){",
            "        if(op[i]=='Q')printf(\"%d\\n\",b[TR.ask(Q[i].x,Q[i].y,Q[i].k)]);",
            "        else TR.add(Q[i].x,-1),A[Q[i].x]=Q[i].y,TR.add(Q[i].x,1);",
            "    }",
            "}",
            ""
        ],
        "description": "插入 树套树-单修权值，区间第k小"
    }
}