//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数列P2710",
        "body": [
            "#include<algorithm>",
            "#include<cstring>",
            "#include<cstdio>",
            "#include<queue>",
            "#define LL long long",
            "#define Re register int",
            "using namespace std;",
            "const int N=2e5+3,inf=1e9;",
            "int n,x,y,z,T,A[N];char op[20];",
            "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 Splay{",
            "\t#define pl (tr[p].ps[0])",
            "\t#define pr (tr[p].ps[1])",
            "\t#define pf (tr[p].fa)",
            "\t#define pv (tr[p].v)",
            "\tint O,root,Q[N];queue<int>D;",
            "\tstruct QAQ{int v,S,fa,max,lmax,rmax,size,ps[2];bool tag,turn;}tr[N];",
            "\tinline void pushup(Re p){",
            "\t\ttr[p].S=tr[pl].S+tr[pr].S+pv;",
            "\t\ttr[p].size=tr[pl].size+tr[pr].size+1;",
            "\t\ttr[p].lmax=max(tr[pl].lmax,tr[pl].S+pv+tr[pr].lmax);",
            "\t\ttr[p].rmax=max(tr[pr].rmax,tr[pr].S+pv+tr[pl].rmax);",
            "\t\ttr[p].max=max(tr[pl].rmax+pv+tr[pr].lmax,max(tr[pl].max,tr[pr].max));",
            "\t}",
            "\tinline void updata(Re p){tr[p].turn^=1,swap(pl,pr),swap(tr[p].lmax,tr[p].rmax);}",
            "\tinline void updata(Re p,Re v){",
            "\t\ttr[p].tag=1,tr[p].S=(pv=v)*tr[p].size;",
            "\t\tif(v>0)tr[p].lmax=tr[p].rmax=tr[p].max=tr[p].S;",
            "\t\telse tr[p].lmax=tr[p].rmax=0,tr[p].max=v;",
            "\t}",
            "\tinline void pushdown(Re p){",
            "\t\tif(tr[p].tag){",
            "\t\t\tif(pl)updata(pl,pv);",
            "\t\t\tif(pr)updata(pr,pv);",
            "\t\t\ttr[p].tag=tr[p].turn=0;",
            "\t\t}",
            "\t\tif(tr[p].turn){",
            "\t\t\tif(pl)updata(pl);",
            "\t\t\tif(pr)updata(pr);",
            "\t\t\ttr[p].turn=0;",
            "\t\t}",
            "\t}",
            "\tinline int which(Re p){return tr[pf].ps[1]==p;}",
            "\tinline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}",
            "\tinline void rotate(Re p){",
            "\t\tRe fa=pf,fas=which(p);",
            "\t\tRe pa=tr[fa].fa,pas=which(fa);",
            "\t\tRe x=tr[p].ps[fas^1];",
            "\t\tconnect(x,fa,fas),connect(fa,p,fas^1),connect(p,pa,pas);",
            "\t\tpushup(fa),pushup(p);",
            "\t}",
            "\tinline void splay(Re p,Re to){",
            "\t\tRe x=p,t=0;Q[++t]=x;",
            "\t\twhile(tr[x].fa)Q[++t]=x=tr[x].fa;",
            "\t\twhile(t)pushdown(Q[t--]);",
            "\t\tfor(Re fa;pf!=to;rotate(p))",
            "\t\t\tif(tr[fa=pf].fa!=to)rotate(which(p)==which(fa)?fa:p);",
            "\t\tif(!to)root=p;",
            "\t}",
            "\tinline void CL(Re p){",
            "\t\ttr[p].size=tr[p].turn=tr[p].tag=tr[p].lmax=tr[p].rmax=tr[p].S=pv=pf=pl=pr=0,tr[p].max=-inf;",
            "\t}",
            "\tinline int New(){",
            "\t\tRe p;",
            "\t\tif(D.empty())p=++O;",
            "\t\telse p=D.front(),D.pop();",
            "\t\tCL(p),tr[p].size=1;return p;",
            "\t}",
            "\tinline void build(Re &p,Re L,Re R,Re fa){",
            "\t\tif(L>R)return;Re mid=(L+R)>>1;p=New(),pv=A[mid],pf=fa;",
            "\t\tbuild(pl,L,mid-1,p),build(pr,mid+1,R,p);",
            "\t\tpushup(p);",
            "\t}",
            "\tinline void recycle(Re p){",
            "\t\tif(pl)recycle(pl);",
            "\t\tif(pr)recycle(pr);",
            "\t\tD.push(p),CL(p);",
            "\t}",
            "\tinline int find(Re p,Re K){",
            "\t\tpushdown(p);",
            "\t\tif(K<=tr[pl].size)return find(pl,K);",
            "\t\treturn K<=tr[pl].size+1?p:find(pr,K-tr[pl].size-1);",
            "\t}",
            "\tinline int split(Re L,Re R){",
            "\t\tRe p=find(root,L-1),q=find(root,R+1);",
            "\t\tsplay(p,0),splay(q,p);return tr[q].ps[0];",
            "\t}",
            "\tinline void insert(Re st,Re m){",
            "\t\tfor(Re i=1;i<=m;++i)in(A[i]);",
            "\t\tRe rt=0;build(rt,1,m,0);",
            "\t\tRe p=find(root,st),q=find(root,st+1);",
            "\t\tsplay(p,0),splay(q,p);",
            "\t\tconnect(rt,q,0),pushup(q),pushup(p);",
            "\t}",
            "\tinline void erase(Re L,Re R){",
            "\t\tRe p=split(L,R),fa=pf;",
            "\t\ttr[fa].ps[0]=pf=0,recycle(p);",
            "\t\tpushup(fa),pushup(tr[fa].fa);",
            "\t}",
            "\tinline int ask(Re L,Re R){return tr[split(L,R)].S;}",
            "\tinline int ask_max(Re L,Re R){return tr[split(L,R)].max;}",
            "\tinline void change(Re L,Re R,Re v){",
            "\t\tRe p=split(L,R);updata(p,v),pushup(pf),pushup(tr[pf].fa);",
            "\t}",
            "\tinline void reverse(Re L,Re R){",
            "\t\tRe p=split(L,R);",
            "\t\tif(!tr[p].tag)updata(p),pushup(pf),pushup(tr[pf].fa);",
            "\t}",
            "}TR;",
            "int main(){",
            "//\tfreopen(\"123.txt\",\"r\",stdin);",
            "\tin(n),in(T),TR.tr[0].max=A[1]=A[n+2]=-inf;",
            "\tfor(Re i=2;i<=n+1;++i)in(A[i]);",
            "\tTR.build(TR.root,1,n+2,0);",
            "\twhile(T--){",
            "\t\tscanf(\"%s\",op);",
            "        if(op[0]=='M'&&op[2]=='X')in(x),in(y),++x,printf(\"%d\\n\",TR.ask_max(x,x+y-1));",
            "\t\telse if(op[0]=='G'&&(int)strlen(op)==3)in(x),++x,printf(\"%d\\n\",TR.ask(x,x));",
            "\t\telse{",
            "\t\t\tin(x),in(y),++x;",
            "\t        if(op[0]=='I')TR.insert(x,y);",
            "\t        if(op[0]=='D')TR.erase(x,x+y-1);",
            "\t        if(op[0]=='M')in(z),TR.change(x,x+y-1,z);",
            "\t        if(op[0]=='R')TR.reverse(x,x+y-1);",
            "\t        if(op[0]=='G')printf(\"%d\\n\",TR.ask(x,x+y-1));",
            "\t\t}",
            "\t}",
            "}",
            ""
        ],
        "description": "插入 Splay"
    }
}