Removal

树状数组

$根据题意，可以看出可以把原题变成一条链，将询问按左端点排序，从1-2n-1扫，再进行树状数组（遇到一个数，就先加进树状数组，如果前面出现过再-1），用树状数组求和统计答案$

#include<bits/stdc++.h>
using namespace std;const int N=2e6+5;
int n,Q,a[N];
int tre[N],lst[N];
struct ask{int l,r,id,ans;
}q[N];
int lowbit(int x){return x&(-x);
}
bool cmp(ask x,ask y)
{return x.r<y.r;
}
bool cmp2(ask x,ask y){return x.id<y.id;
}
void uppdate(int x,int val){for(int s=x;s<=n;s+=lowbit(s)) tre[s]+=val;}
int query(int x){int ans=0;for(int s=x;s>0;s-=lowbit(s)) ans+=tre[s];return ans;}
int main(){scanf("%d%d",&n,&Q);for(int i=1;i<=n;i++){scanf("%d",&a[i]);a[i+n]=a[i];}for(int i=1;i<=Q;i++){scanf("%d%d",&q[i].r,&q[i].l);q[i].r+=n;q[i].id=i;}n=n*2;sort(q+1,q+Q+1,cmp);int ak=1;for(int i=1;i<=n;i++){uppdate(i,1);if(lst[a[i]]) uppdate(lst[a[i]],-1);lst[a[i]]=i;while(i==q[ak].r) q[ak].ans=query(q[ak].r)-query(q[ak].l-1),ak++;}sort(q+1,q+Q+1,cmp2);for(int i=1;i<=Q;i++){ printf("%d\n",q[i].ans);}
}