//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.8seg",
        "body": [
            "#include<iostream>",
            "#include<stack>",
            "#include<string>",
            "#include<set>",
            "#include<algorithm>",
            "#include<queue>",
            "#include<map>",
            "#include<vector>",
            "#include<cmath>",
            "using namespace std;",
            "//#define int long long",
            "const int N=1e6+5;",
            "int n,m,cnt,root[N],last[N];",
            "int ls[N<<5],rs[N<<5],w[N<<5];",
            "int update(int lu,int l,int r,int x){",
            "\tint u=++cnt;",
            "\tls[u]=ls[lu],rs[u]=rs[lu],w[u]=w[lu];w[u]++;",
            "\tif(l==r)return u;",
            "\tint mid=(l+r)>>1;",
            "\tif(x<=mid)ls[u]=update(ls[lu],l,mid,x);",
            "\telse rs[u]=update(rs[lu],mid+1,r,x);",
            "\treturn u;",
            "}",
            "int query(int u1,int u2,int l,int r,int x){",
            "\tif(l>=x)return 0;",
            "\tif(r<x)return w[u2]-w[u1];",
            "\tint mid=(l+r)>>1;",
            "\treturn query(ls[u1],ls[u2],l,mid,x)+query(rs[u1],rs[u2],mid+1,r,x);",
            "}",
            "void solve(){",
            "\tcin>>n;",
            "\tfor(int i=1;i<=n;i++){",
            "\t\tint x;",
            "\t\tcin>>x;",
            "\t\tif(last[x])root[i]=update(root[i-1],0,n,last[x]);",
            "\t\telse root[i]=update(root[i-1],0,n,0);\t",
            "\t\tlast[x]=i;\t",
            "\t}",
            "\tcin>>m;",
            "\twhile(m--){",
            "\t\tint l,r;",
            "\t\tcin>>l>>r;",
            "\t\tcout<<query(root[l-1],root[r],0,n,l)<<'\\n';",
            "\t}",
            "}",
            "signed main()",
            "{",
            "    ios::sync_with_stdio(false);",
            "    cin.tie(0),cout.tie(0);",
            "    int T=1;",
            "    while(T--)solve();",
            "}",
            "/*",
            "*/"
        ],
        "description": "插入 区间元素数"
    }
}