一眼又是个莫队……
首先看这时间/空间复杂度，线段树/主席树就别想了……
然后么……zcy就有点傻了……
于是zcy看了下hzwer，感觉受教育了。
分块的调块大小真是玄学设计。
有没有一种方法在修改上能够比线段树更快，同时又能相比暴力较快地回答询问呢？
我们可以用分块，把序列分成(nsqrt(n)块，修改的复杂度是)O(1)(，回答询问的复杂度是)O(nsqrt(n))%
随手写了一发，竟然上去就MLE了……
什么鬼题空间只有28MB……
#include<bits/stdc++.h>
#define inf 1000000007
#define N 1000005
using namespace std;
int n,m,size,cnt,a[100005],ans[1000005];
int rt[100005],L[2010],R[2010],c[100005],cntv[2010];
struct Query{int l,r,a,b,id;}q[1000005];
bool operator<(Query x,Query y){
if(rt[x.l]==rt[y.l])return x.r<y.r;
else return x.l<y.l;
}
int query(int x,int y){
int tmp=0,l=rt[x],r=rt[y];
for(int i=l+1;i<r;i++)tmp+=cntv[i];
if(l==r){for(int i=x;i<=y;i++)if(c[i])++tmp;}
else{
for(int i=x;i<=R[l];i++)if(c[i])++tmp;
for(int i=L[r];i<=y;i++)if(c[i])++tmp;
}
return tmp;
}
inline void del(int x){c[x]--;if(!c[x])cntv[rt[x]]--;}
inline void add(int x){c[x]++;if(c[x]==1)cntv[rt[x]]++;}
void solve(){
int l=1,r=0;
for(int i=1;i<=m;i++){
while(l<q[i].l)del(a[l]),l++;
while(r>q[i].r)del(a[r]),r--;
while(l>q[i].l)l--,add(a[l]);
while(r<q[i].r)r++,add(a[r]);
ans[q[i].id]=query(q[i].a,q[i].b);
}
}
inline int read(){
int f=1,x=0;char ch;
do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
return f*x;
}
int main(){
n=read();m=read();size=(int)sqrt(n/2);
cnt=(n/size)+(n%size!=0);
for(int i=1;i<=n;i++)rt[i]=(i-1)/size+1;
for(int i=1;i<=n;i++){
R[rt[i]]=i;
if(!L[rt[i]])L[rt[i]]=i;
}
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=m;i++){
q[i].l=read();q[i].r=read();
q[i].a=read();q[i].b=read();
q[i].id=i;
}
sort(q+1,q+m+1);
solve();
for(int i=1;i<=m;i++)printf("%d
",ans[i]);
return 0;
}