//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.9区间众数",
        "body": [
            "#include<iostream>",
            "#include<cstdio>",
            "#include<cmath>",
            "#include<algorithm>",
            "#include<cstring>",
            "using namespace std;",
            "const int u=40010;",
            "int c[40][40][u],f[40][40],d[40][40],a[u],b[u],fa[u],fb[u],st[40],ed[40];",
            "int n,m,t,l,tot,i,j,k,x,y,ans,L,R,cnt,num;",
            "",
            "void prework()",
            "{",
            "\tt=(int)pow(n*1.0,1.0/3);",
            "\tif(t) l=n/t;",
            "\tfor(i=1;i<=t;i++) st[i]=(i-1)*l+1,ed[i]=i*l;",
            "\tif(ed[t]<n) st[t+1]=ed[t]+1,ed[++t]=n;",
            "\tmemcpy(fa,a,sizeof(a));",
            "\tsort(fa+1,fa+n+1);",
            "\tfor(i=1;i<=n;i++)",
            "\t\tif(i==1||fa[i]!=fa[i-1]) fb[++tot]=fa[i];",
            "\tfor(i=1;i<=n;i++) b[i]=lower_bound(fb+1,fb+tot+1,a[i])-fb;",
            "\tfor(i=1;i<=t;i++)",
            "\t\tfor(j=i;j<=t;j++)",
            "\t\t{",
            "\t\t\tfor(k=st[i];k<=ed[j];k++) c[i][j][b[k]]++;",
            "\t\t\tfor(k=1;k<=tot;k++)",
            "\t\t\t\tif(c[i][j][k]>f[i][j]||c[i][j][k]==f[i][j]&&k<d[i][j])",
            "\t\t\t\t\tf[i][j]=c[i][j][k],d[i][j]=k;",
            "\t\t}",
            "}",
            "",
            "inline void update(int i)",
            "{",
            "\tc[L][R][b[i]]++;",
            "\tif(c[L][R][b[i]]>cnt||c[L][R][b[i]]==cnt&&b[i]<num) cnt=c[L][R][b[i]],num=b[i];",
            "}",
            "",
            "int solve(int x,int y)",
            "{",
            "\tint i,l,r;",
            "\tif(x>y) swap(x,y);",
            "\tfor(i=1;i<=t;i++) if(x<=ed[i]) {l=i; break;}",
            "\tfor(i=t;i;i--) if(y>=st[i]) {r=i; break;}",
            "\tif(l+1<=r-1) L=l+1,R=r-1; else L=R=0;",
            "\tcnt=f[L][R],num=d[L][R];",
            "\tif(l==r)",
            "\t{",
            "\t\tfor(i=x;i<=y;i++) update(i);",
            "\t\tfor(i=x;i<=y;i++) c[L][R][b[i]]--;",
            "\t}",
            "\telse{",
            "\t\tfor(i=x;i<=ed[l];i++) update(i);",
            "\t\tfor(i=st[r];i<=y;i++) update(i);",
            "\t\tfor(i=x;i<=ed[l];i++) c[L][R][b[i]]--;",
            "\t\tfor(i=st[r];i<=y;i++) c[L][R][b[i]]--;",
            "\t}",
            "\treturn fb[num];",
            "}",
            "",
            "int main()",
            "{",
            "\tcin>>n>>m;",
            "\tfor(i=1;i<=n;i++) scanf(\"%d\",&a[i]);",
            "\tprework();",
            "\tfor(i=1;i<=m;i++)",
            "\t{",
            "\t\tscanf(\"%d%d\",&x,&y);",
            "\t\tans=solve((x+ans-1)%n+1,(y+ans-1)%n+1);",
            "\t\tprintf(\"%d\\n\",ans);",
            "\t}",
            "\treturn 0;",
            "}",
            ""
        ],
        "description": "插入 蒲公英参考程序"
    }
}