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

{
    "ST表求区间最值": {
        "prefix": "acm-2.6RMQ",
        "body": [
            "#include<algorithm>",
            "#include<cstring>",
            "#include<cstdio>",
            "using namespace std;",
            "const int N=1e5+3,inf=2147483647;",
            "int i,j,n,k,m,a[N],lg[N],f1[N][18],f2[N][18];",
            "int main(){",
            "    scanf(\"%d%d\",&n,&k);",
            "    for(i=0;i<=17;i++)",
            "        for(j=0;j<=n+1;j++)",
            "            f1[i][j]=-inf,f2[i][j]=inf;",
            "    lg[1]=0;for(i=2;i<=n;i++)lg[i]=lg[i>>1]+1;m=lg[n];",
            "    for(i=1;i<=n;f2[i][0]=f1[i][0],i++)scanf(\"%d\",&f1[i][0]);",
            "    for(i=1;i<=m;i++)",
            "        for(j=1;j+(1<<i)-1<=n;j++)",
            "            f1[j][i]=max(f1[j][i-1],f1[j+(1<<i-1)][i-1]),f2[j][i]=min(f2[j][i-1],f2[j+(1<<i-1)][i-1]);",
            "    m=lg[k];",
            "    for(i=1;i+k-1<=n;i++)printf(\"%d %d\\n\",max(f1[i][m],f1[i+k-(1<<m)][m]),min(f2[i][m],f2[i+k-(1<<m)][m]));",
            "}",
            ""
        ],
        "description": "插入 ST表求区间最值"
    }
}