刘嘉柚 • 3个月前
typedef long long LL;
typedef unsigned long long ULL;
using namespace FastIo;
#define NUMBER1 500000
#define P(A) A=-~A
#define fione_i(begin,end) for(register int i=begin;i<=end;P(i))
int n,m,fk,cnt[NUMBER1+5],a[NUMBER1+5],b[NUMBER1+5],ans[NUMBER1+5],sum(0);
struct ASK{
int l,r,id;
bool operator<(const ASK &A)const{return l/fk==A.l/fk?r<A.r:l<A.l;}
}ask[NUMBER1+5];
inline void add(int k){
P(cnt[k]);
if(cnt[k]==2)P(sum);
else if(cnt[k]==3)--sum;
}
inline void del(int k){
--cnt[k];
if(cnt[k]==2)P(sum);
else if(cnt[k]==1)--sum;
}
signed main(){
int l(1),r(0),m1;
qrw.read(n);
qrw.read(m);
fk=sqrt(n);
fione_i(1,n){
qrw.read(a[i]);
b[i]=a[i];
}
std::sort(b+1,b+1+n);
m1=std::unique(b+1,b+1+n)-b;
fione_i(1,n)a[i]=std::lower_bound(b+1,b+1+m1,a[i])-b;
fione_i(1,m){
qrw.read(ask[i].l);
qrw.read(ask[i].r);
ask[i].id=i;
}
std::sort(ask+1,ask+1+m);
fione_i(1,m){
while(l<ask[i].l)del(a[l++]);
while(l>ask[i].l)add(a[--l]);
while(r>ask[i].r)del(a[r--]);
while(r<ask[i].r)add(a[++r]);
ans[ask[i].id]=sum;
}
fione_i(1,m)qrw.write(ans[i]);
fsh;
exit(0);
return 0;
}
评论: