传送门
题意：多组询问，问区间[l,r]中权值在[a,b]间的数的种类数。
看了一眼大家应该都知道要莫队了吧。
然后很容易想到用树状数组优化修改和查询做到O(mnlogamax)O(m\sqrt nlog_{a_{max}})O(mnlogamax)的时间复杂度。
然后发现可以上一波权值分块，这样的话可以平衡结合降低时间复杂度到O(mn+mamax)O(m\sqrt n+m\sqrt {a_{max}})O(mn+mamax)
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
const int N=1e5+5,M=1e6+5;
int n,m,sum[N][2],cnt[N],a[N],ans[M],sqr1,sqr2,mx=0;
struct Node{int l,r,a,b,id;}qry[M];
inline int idx(int p,int blo){return (p-1)/blo+1;}
inline bool cmp(const Node&a,const Node&b){
int ia=idx(a.l,sqr1),ib=idx(b.l,sqr1);
return ia==ib?a.r<b.r:ia<ib;
}
inline void add(int p){
int val=a[p],blo=idx(val,sqr2);
++sum[blo][0],++cnt[a[p]];
if(cnt[a[p]]==1)++sum[blo][1];
}
inline void del(int p){
int val=a[p],blo=idx(val,sqr2);
--sum[blo][0],--cnt[a[p]];
if(!cnt[a[p]])--sum[blo][1];
}
inline int query(int val){
int blo=idx(val,sqr2),ret=0;
for(ri i=blo-1;i;--i)ret+=sum[i][1];
for(ri i=(blo-1)*sqr2+1;i<=val;++i)ret+=cnt[i]?1:0;
return ret;
}
int main(){
freopen("lx.in","r",stdin);
n=read(),m=read();
for(ri i=1;i<=n;++i)a[i]=read(),mx=max(mx,a[i]);
sqr1=sqrt(n+0.5),sqr2=sqrt(mx+0.5);
for(ri i=1;i<=m;++i)qry[i].l=read(),qry[i].r=read(),qry[i].a=read(),qry[i].b=read(),qry[i].id=i;
sort(qry+1,qry+m+1,cmp);
int pl=1,pr=0;
for(ri tt=1;tt<=m;++tt){
while(pl<qry[tt].l)del(pl++);
while(pl>qry[tt].l)add(--pl);
while(pr<qry[tt].r)add(++pr);
while(pr>qry[tt].r)del(pr--);
ans[qry[tt].id]=query(qry[tt].b)-query(qry[tt].a-1);
}
for(ri i=1;i<=m;++i)cout<<ans[i]<<'\n';
return 0;
}