题意

给出一个数列，有$m$次询问，求$[l,r]$之间有多少个出现次数$\ge 2$的数

数据范围：$1 \le n,m \le 2 \cdot 10^6$

题解

对于每个区间，若一个数出现了$\ge 2$次，将其贡献计在第$2$个上（因为第$1$个无法产生贡献，而$\ge 2$与$=2$产生的贡献并无区别）
这样，记录一个$nxt[i]$表示下一个与$i$相等的数出现的位置
将询问离线，按左端点排序，从左往右扫；若当前点$i$已经扫过，将$nxt[i]$的贡献取消，若$nxt[nxt[i]]$存在，则为其加上贡献
在扫描的同时计算答案，用树状数组维护前缀和计算

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2e6+10;
int n,c,m,l,r;
int a[N],nxt[N],lst[N],cnt[N],T[N],ans[N];
struct query{
    int l,r,id;
    inline bool operator < (const query& x) const{
        return l<x.l;
    }
} q[N];
inline int lowbit(int x){
    return x&-x;
}
inline void update(int p,int k){
    for(;p<=n;p+=lowbit(p))
        T[p]+=k;
}
inline int query(int p){
    int res=0;
    for(;p;p-=lowbit(p))
        res+=T[p];
    return res;
}
int main(){
    scanf("%d%d%d",&n,&c,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].id=i;
    }
    for(int i=n;i;i--){
        nxt[i]=lst[a[i]];
        lst[a[i]]=i;
    }
    for(int i=1;i<=n;i++)
        if(++cnt[a[i]]==2)
            update(i,1);
    sort(q+1,q+m+1);
    for(int i=1,l=1;i<=m;i++){
        for(;l<q[i].l;l++)
            if(nxt[l]){
                update(nxt[l],-1);
                if(nxt[nxt[l]])
                    update(nxt[nxt[l]],1);
            }
        ans[q[i].id]=query(q[i].r)-query(q[i].l-1);
    }
    for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    return 0;
}