难度：紫

算法：莫队

莫队。

维护每个数是否出现，$i$ 在 $l$ 到 $r$ 中出现则记 $t_i=1$，否则 $t_i=0$。

那么答案就是 $\sum_{i=a}^{b} t_i$。

使用树状数组维护 $t$。

取块长 $\frac{n}{\sqrt m}$，时间复杂度 $O(n\sqrt m\log n)$，勉强能过。

#include<bits/stdc++.h>
using namespace std;
struct tr{
	int s[100010],n=1e5;
	int lowbit(int x){
		return x&(-x);
	}
	void add(int x,int c){
		while(x<=n){
			s[x]+=c;
			x+=lowbit(x);
		}
	}
	int que(int x){
		int ans=0;
		while(x){
			ans+=s[x];
			x-=lowbit(x);
		}
		return ans;
	}
}t;
int sz;
struct nd{
	int l,r,a,b,v;
	bool operator<(nd a){
		if(l/sz!=a.l/sz) return l<a.l;
		if((l/sz)&1) return r<a.r;
		else return r>a.r;
	}
}q[1000010];
int ans[1000010],cnt[100010],res;
int n,m,a[100010],l=1,r;
void add(int x){
	if(cnt[x]==0){
		t.add(x,1);
	}
	cnt[x]++;
}
void del(int x){
	cnt[x]--;
	if(cnt[x]==0){
		t.add(x,-1);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	sz=n/int(sqrt(m));
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d%d%d",&q[i].l,&q[i].r,&q[i].a,&q[i].b);
		q[i].v=i;
	}
	sort(q+1,q+m+1);
	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--]);
		ans[q[i].v]=t.que(q[i].b)-t.que(q[i].a-1);
	}
	for(int i=1;i<=m;i++){
		printf("%d\n",ans[i]);
	}
}