https://ac.nowcoder.com/acm/contest/19684/B

 #include<bits/stdc++.h>
using namespace std;
const int N=2000005;
int pre[N],tot,a[N];
int n,m,l,r,c[N],ans[N];
struct query_node
{
    int id;
    int pos;
};
vector<query_node>q[N];
int lowbit(int x)
{
        return x&-x;
}
void change(int x,int y)
{
    while(x<=n)
    {
        c[x]+=y;
        x+=lowbit(x);
    }
    return ;
}
int sum(int x)
{
    int ans=0;
    while(x)
    {
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>l>>r;
        q[r].push_back({i,l});
    }
    for(int i=1;i<=n;i++)
    {
        if(pre[a[i]])//如果a[i]这个数字出现过
        {
            change(pre[a[i]],-1);//上一次出现的位置右边都减一
            change(i,1);//本次的右边都+1
            pre[a[i]]=i;//更新最新位置
        }
        else
        {
            change(i,1);
            pre[a[i]]=i;    
        }
        //离线询问，，赋值询问
         //询问的是以i为右端点的区间
        for(auto j:q[i])
            {
                ans[j.id]=sum(i)-sum(j.pos-1);
            }

    }
    for(int i=1;i<=m;i++)
        {
        cout<<ans[i]<<"\n";
        }


    return 0;
}

https://ac.nowcoder.com/acm/contest/19684/C

#include<bits/stdc++.h>
using namespace std;
const int N=2000005;
int pre[N][2],a[N],c[N];
int l,r,m,ans[N],n,s;
struct query_node
{
    int id;
    int pos;
};
vector<query_node>q[N];
int lowbit(int x)
{
    return x&-x;
}
void change(int x,int y)//单点修改
{
    while(x<=n)
    {
        c[x]+=y;
        x+=lowbit(x);
    }
}
int sum(int x)//单点查询
{
    int ans=0;
    while(x)
    {
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}

int main()
{   cin>>n>>s>>m;
    //pre[n][1]//表示第a[n]个数字第二次出现的位置
    //pre[n][0]表示第a[n]个数字第一次出现的位置
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=m;i++)
    {
        cin>>l>>r;
        q[r].push_back({i,l});
    }
    for(int i=1;i<=n;i++)
    {
        if(pre[a[i]][1])
        {
            change(pre[a[i]][1],-1);
            change(pre[a[i]][0],1);
        }
        else if(pre[a[i]][0])
        {
            change(pre[a[i]][0],1);
        }
        pre[a[i]][1]=pre[a[i]][0];
        pre[a[i]][0]=i;
        for(auto j : q[i])
        {
            ans[j.id]=sum(i)-sum(j.pos-1);
        }
    }
    for(int i=1;i<=m;i++)
    {
        cout<<ans[i]<<"\n";
    }


    return 0;
}