//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.6区间排序 P2824",
        "body": [
            "#include<algorithm>",
            "#include<cstring>",
            "#include<cstdio>",
            "#include<set>",
            "#define LL long long",
            "#define Re register int",
            "#define IT set<QAQ>::iterator",
            "using namespace std;",
            "const int N=1e5+3;",
            "int n,m,l,r,T,op,A[N],tmp[N],cnt[N],Ans[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;",
            "}",
            "struct QAQ{",
            "\tint l,r;mutable int pt,op; ",
            "\tQAQ(Re L=0,Re R=0,Re OP=0,Re PT=0){l=L,r=R,op=OP,pt=PT;};",
            "\tinline bool operator<(const QAQ &O)const{return l<O.l;}",
            "};",
            "set<QAQ>s;",
            "struct Segment_Tree{",
            "\t#define pl tr[p].lp",
            "\t#define pr tr[p].rp",
            "\t#define mid ((L+R)>>1)",
            "\tint O;",
            "\tstruct QAQ{int S,lp,rp;}tr[N*60];",
            "\tinline void pushup(Re p){tr[p].S=tr[pl].S+tr[pr].S;}",
            "\tinline void change(Re &p,Re L,Re R,Re x){",
            "\t\tp=++O;",
            "\t\tif(L==R){tr[p].S=1;return;}",
            "\t\tif(x<=mid)change(pl,L,mid,x);",
            "\t\telse change(pr,mid+1,R,x);",
            "\t\tpushup(p);",
            "\t}",
            "\tinline int merge(Re p,Re q,Re L,Re R){",
            "\t\tif(!p||!q)return p+q;",
            "\t\tif(L==R){tr[p].S+=tr[q].S;return p;}",
            "\t\tpl=merge(pl,tr[q].lp,L,mid);",
            "\t\tpr=merge(pr,tr[q].rp,mid+1,R);",
            "\t\tpushup(p);return p;",
            "\t}",
            "\tinline void split1(Re &p,Re q,Re L,Re R,Re k){// 取q中的前k个,分到新节点p",
            "\t\ttr[p=++O].S=tr[q].S-k,tr[q].S=k;",
            "\t\tif(L==R)return;",
            "\t\tRe tmp=tr[tr[q].lp].S;",
            "\t\tif(k>tmp)split1(pr,tr[q].rp,mid+1,R,k-tmp);// q左子树全部分给p,只剩右子树",
            "\t\telse pr=tr[q].rp,tr[q].rp=0;// 右子树全部分给p",
            "\t\tif(k<tmp)split1(pl,tr[q].lp,L,mid,k);// q的右子树全部分给p,只剩左子树",
            "\t}",
            "\tinline void split2(Re &p,Re q,Re L,Re R,Re k){// 取q中的后k个,分到新节点p",
            "\t\ttr[p=++O].S=tr[q].S-k,tr[q].S=k;",
            "\t\tif(L==R)return;",
            "\t\tRe tmp=tr[tr[q].rp].S;",
            "\t\tif(k>tmp)split2(pl,tr[q].lp,L,mid,k-tmp);// q的右子树全部分给p,只剩左子树",
            "\t\telse pl=tr[q].lp,tr[q].lp=0;// 左子树全部分给p",
            "\t\tif(k<tmp)split2(pr,tr[q].rp,mid+1,R,k);// q左子树全部分给p,只剩右子树",
            "\t}",
            "\tinline void dfs(Re p,Re L,Re R){",
            "\t\tif(!p)return;",
            "\t\tif(L==R){cnt[tmp[++tmp[0]]=L]=tr[p].S;return;}",
            "\t\tdfs(pl,L,mid),dfs(pr,mid+1,R);",
            "\t}",
            "}T1;",
            "inline IT split(Re w){",
            "\tIT it=s.lower_bound(QAQ(w));",
            "\tif(it!=s.end()&&it->l==w)return it;",
            "\t--it;",
            "\tRe L=it->l,R=it->r,op=it->op,pt=it->pt,ptt=0;",
            "\ts.erase(it);",
            "\tif(op)T1.split1(ptt,pt,1,m,w-1-L+1);",
            "\telse T1.split2(ptt,pt,1,m,w-1-L+1);",
            "\ts.insert(QAQ(L,w-1,op,pt));",
            "\treturn s.insert(QAQ(w,R,op,ptt)).first;",
            "}",
            "inline void assign(Re l,Re r,Re op){",
            "\tif(l==r)return;",
            "\tIT itr=split(r+1),itl=split(l),it=itl;",
            "\tRe pt=0;",
            "\twhile(it!=itr)pt=T1.merge(pt,it->pt,1,m),it->pt=0,++it;",
            "\ts.erase(itl,itr),s.insert(QAQ(l,r,op,pt));",
            "}",
            "int main(){",
            "//\tfreopen(\"123.txt\",\"r\",stdin);",
            "\tin(n),in(T),m=n;",
            "\tfor(Re i=1;i<=n;++i)in(A[i]);",
            "\ts.insert(QAQ(n+1,n+1));",
            "\tfor(Re i=1;i<=n;++i){",
            "\t\tQAQ tmp(i,i,0,0);T1.change(tmp.pt,1,m,A[i]),s.insert(tmp);",
            "\t}",
            "\twhile(T--)in(op),in(l),in(r),op^=1,assign(l,r,op);",
            "\tIT itl=s.lower_bound(QAQ(1)),itr=s.lower_bound(QAQ(n+1));",
            "\twhile(itl!=itr){",
            "\t\ttmp[0]=0,T1.dfs(itl->pt,1,m);",
            "\t\tif(itl->op)for(Re i=1;i<=tmp[0];++i)",
            "\t\t\tfor(Re j=1;j<=cnt[tmp[i]];++j)",
            "\t\t\t\tAns[++Ans[0]]=tmp[i];",
            "\t\telse for(Re i=tmp[0];i>=1;--i)",
            "\t\t\tfor(Re j=1;j<=cnt[tmp[i]];++j)",
            "\t\t\t\tAns[++Ans[0]]=tmp[i];",
            "\t\t++itl;",
            "\t}",
            "\tin(op),printf(\"%d\\n\",Ans[op]);",
            "}",
            ""
        ],
        "description": "插入 线段树分裂-分裂区间前后k个"
    }
}