//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<algorithm>",
            "#include<cstring>",
            "#include<cstdio>",
            "#include<cmath>",
            "#define Re register int",
            "using namespace std;",
            "const int N=2e5+3,M=2e5+3,INF=1e6+3;",
            "int n,x,y,T,TQ,TC,BL,ans,a[N],Ans[M],cnt[INF];char op;",
            "struct Query{",
            "    int l,r,id,time;",
            "    inline bool operator<(const Query &O)const{",
            "        Re B1=l/BL,B2=O.l/BL,B3=r/BL,B4=O.r/BL;",
            "        return B1!=B2?B1<B2:(B3!=B4?B3<B4:time<O.time);",
            "    }",
            "}Q[N];",
            "struct Change{int w,co;}C[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;",
            "}",
            "inline void add(Re x){ans+=!cnt[x]++;}",
            "inline void del(Re x){ans-=!--cnt[x];}",
            "int main(){",
            "//    freopen(\"123.txt\",\"r\",stdin);",
            "    in(n),in(T),BL=pow(n,2.0/3.0);",
            "    for(Re i=1;i<=n;++i)in(a[i]);",
            "    for(Re i=1;i<=T;++i){",
            "    \tscanf(\" %c\",&op);",
            "    \tin(x),in(y);",
            "    \tif(op=='Q')++TQ,Q[TQ]=(Query){x,y,TQ,TC};",
            "    \telse C[++TC]=(Change){x,y};",
            "\t}",
            "    sort(Q+1,Q+TQ+1);",
            "    Re nowL=1,nowR=0,nowT=0;",
            "    for(Re i=1;i<=TQ;++i){",
            "        while(nowL<Q[i].l)del(a[nowL++]);",
            "        while(nowL>Q[i].l)add(a[--nowL]);",
            "        while(nowR>Q[i].r)del(a[nowR--]);",
            "        while(nowR<Q[i].r)add(a[++nowR]);",
            "        while(nowT<Q[i].time){",
            "        \tRe w=C[++nowT].w;",
            "        \tif(nowL<=w&&w<=nowR)del(a[w]),add(C[nowT].co);",
            "        \tswap(a[w],C[nowT].co);",
            "\t\t}",
            "\t\twhile(nowT>Q[i].time){",
            "\t\t\tRe w=C[nowT].w;",
            "        \tif(nowL<=w&&w<=nowR)del(a[w]),add(C[nowT].co);",
            "        \tswap(a[w],C[nowT--].co);",
            "\t\t}",
            "        Ans[Q[i].id]=ans;",
            "    }",
            "    for(Re i=1;i<=TQ;++i)printf(\"%d\\n\",Ans[i]);",
            "}",
            ""
        ],
        "description": "插入 带修莫队"
    }
}