题目：

离线处理，注意排序方式

 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#define ll long long
const int maxn=320010;
const int Block=sqrt(maxn);
const int tt=1;//数字出现的最少次数
using namespace std;
struct node
{
    int id;
    int l,r;
}pos[200010];

int n,q,a[maxn],cnt[1000100],answer=0,l,r,ans[200010];

bool cmp(node a,node b)
{
    if(a.l/Block!=b.l/Block)
        return a.l/Block<b.l/Block;
    return a.r<b.r;
}
void add(int positoin)
{
    cnt[a[positoin]]++;
    if(cnt[a[positoin]]==tt)
        answer++;
}
void Remove(int positoin)
{
    cnt[a[positoin]]--;
    if(cnt[a[positoin]]==tt-1)
        answer--;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
    {
        scanf("%d %d",&pos[i].l,&pos[i].r);
        pos[i].id=i;
    }
    sort(pos+1,pos+q+1,cmp);
    int cl=1,cr=1;
    for(int i=1;i<=q;i++)
    {
        l=pos[i].l;r=pos[i].r;
        while(cl<l) {
            Remove(cl);
            cl++;
        }
        while(cl>l) {
            add(cl-1);
            cl--;
        }
        while(cr<=r) {
            add(cr);
            cr++;
        }
        while(cr>r+1)
        {
            Remove(cr-1);
            cr--;
        }

        ans[pos[i].id]=answer;
    }
    for(int i=1;i<=q;i++)
        printf("%d\n",ans[i]);
    return 0;
}

 

当然线段树也可以解决

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<stack>
#include<map>
#include<algorithm>
#include<cmath>
#define eps 1e-8
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int a[maxn];
struct node1
{
    int l,r,id;

}q[maxn<<2];
ll e[maxn<<2],sum[maxn<<2];
bool cmp(node1 a,node1 b)
{
    return a.r<b.r;
}
void pushup(int cur)
{
    e[cur]=e[cur<<1]+e[cur<<1|1];
}
void build(int l,int r,int cur)
{
    e[cur]=0;
    if(l==r)
        return;
    int m=l+r>>1;
    build(l,m,cur<<1);
    build(m+1,r,cur<<1|1);
    //pushup(cur);

}
void update(int l,int r,int val,int cur,int pos)
{
    if(l==r)
    {
        if(val==0)
            e[cur]=val;
        else e[cur]=1;
        return;
    }
    int m=l+r>>1;
    if(pos<=m)update(l,m,val,cur<<1,pos);
    else update(m+1,r,val,cur<<1|1,pos);
    pushup(cur);
}
ll query(int l,int r,int cur,int pl,int pr)
{
    if(pl<=l&&r<=pr)
    {
        return e[cur];
    }
    ll ans=0;
    int m=l+r>>1;
    if(pl<=m) ans+=query(l,m,cur<<1,pl,pr);
    if(pr>m)ans+=query(m+1,r,cur<<1|1,pl,pr);
    return ans;
}
map<int,int>mp;
int main()
{
    int T;
    //scanf("%d",&T);
   // while(T--)
    //{
        mp.clear();

        int n,m;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        build(1,n,1);
        scanf("%d",&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&q[i].l,&q[i].r);
            q[i].id=i;
        }
        sort(q+1,q+m+1,cmp);
        int pos=1;

        for(int i=1;i<=m;i++)
        {

            while(q[i].r>=pos)
            {
                if(mp[a[pos]])
                    update(1,n,0,1,mp[a[pos]]);
                mp[a[pos]]=pos;
                update(1,n,a[pos],1,pos);
                pos++;
            }
            sum[q[i].id]=query(1,n,1,q[i].l,q[i].r);
        }
        for(int i=1;i<=m;i++)
        {
            printf("%lld\n",sum[i]);
        }
    //}


    return 0;
}