题目
给定一个序列，多次询问一个区间当中值域在 ([a,b]) 当中的值的种类数。
分析
莫队+值域分块。
首先很明显可以莫队来维护这个区间信息。
然后考虑怎么维护这个 值域在 ([a,b]) 当中的值的种类数。
需要支持 (O(1)) 修改，(O(sqrt{n})) 查询。
显然可以值域分块。
于是修改直接加一就行，然后询问找到块边角暴力，大块直接加个数即可。
时间复杂度 (O(sqrt{n}))。
代码
#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
x=0;char ch=getchar();bool f=false;
while(!isdigit(ch)){if(ch=='-'){f=true;}ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
x=f?-x:x;
return ;
}
template <typename T>
inline void write(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10^48);
return ;
}
const int N=1e5+5,B=405,M=1e6+5;
#define ll long long
int n,m,k;
int bl[N];
int a[N],Ans[M],sum[B],cnt[N];
struct Query{int l,r,x,y,id;}Q[M];
inline void Add(int x){
if(!cnt[x]) sum[bl[x]]++;
cnt[x]++;
return ;
}
inline void Del(int x){
cnt[x]--;
if(!cnt[x]) sum[bl[x]]--;
return ;
}
inline bool Cmp(Query x,Query y){return bl[x.l]^bl[y.l]?bl[x.l]<bl[y.l]:bl[x.l]&1?x.r<y.r:x.r>y.r;}
int main(){
read(n);read(m);
for(int i=1;i<=n;i++) read(a[i]);
const int t=sqrt(n);
for(int i=1;i<=m;i++) read(Q[i].l),read(Q[i].r),read(Q[i].x),read(Q[i].y),Q[i].id=i;
for(int i=1;i<=n;i++) bl[i]=(i-1)/t+1;
sort(Q+1,Q+m+1,Cmp);
int l=1,r=0;
for(int i=1;i<=m;i++){
while(l>Q[i].l) Add(a[--l]);
while(r<Q[i].r) Add(a[++r]);
while(l<Q[i].l) Del(a[l++]);
while(r>Q[i].r) Del(a[r--]);
if(bl[Q[i].x]==bl[Q[i].y]){
int res=0;
for(int k=Q[i].x;k<=Q[i].y;k++) if(cnt[k]) res++;
Ans[Q[i].id]=res;
continue;
}
const int BR1=bl[Q[i].x]*t,BL1=(bl[Q[i].y]-1)*t+1,p=bl[Q[i].x],q=bl[Q[i].y];
int res=0;
for(int k=Q[i].x;k<=BR1;k++) if(cnt[k]) res++;
for(int k=p+1;k<=q-1;k++) res+=sum[k];
for(int k=BL1;k<=Q[i].y;k++) if(cnt[k]) res++;
Ans[Q[i].id]=res;
}
for(int i=1;i<=m;i++) write(Ans[i]),putchar('
');
return 0;
}