14wa,23tle

#include <bits/stdc++.h>

using namespace std;
#define block(i) ((i-1)/sqr+1)
#define N 100005

int n,m,sqr,l=1,r=1,ans[N];
int a[N],st[N],ed[N],exist[N],existblock[N],cnt[N];
struct query{
	int l,r,a,b,id;
	void in(){
		scanf("%d%d%d%d",&l,&r,&a,&b);
	};
}q[N];

bool cmp(query p,query q){
	if(p.l/sqr == q.l/sqr) return p.r<q.r;
	return p.l/sqr<q.l/sqr;
}
void init(){
	sqr=sqrt(n);
	for(int i=1;i<=n;i++) st[block(i)]=0x7fffffff;
	for(int i=1;i<=n;i++){
		st[block(i)]=min(st[block(i)],i);
		ed[block(i)]=max(ed[block(i)],i);
	}
}

void update(int x,int k){
	cnt[x]+=k,exist[x]=(cnt[x]>0);
	if(cnt[x]==1 && k==1) existblock[block(x)]++;
	if(!cnt[x] && k==-1) existblock[block(x)]--;
}

int query(int l,int r){
	int sum=0,bl=block(l),br=block(r);
	if(bl==br){
		for(int i=l;i<=r;i++) sum+=exist[i];
		return sum;
	}
	for(int i=bl+1;i<br;i++) sum+=existblock[i];
	for(int i=l;i<=ed[bl];i++) sum+=exist[i];
	for(int i=st[br];i<=r;i++) sum+=exist[i];
	return sum;
}
int main()
{
	cin>>n>>m;
	init();
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=m;i++) q[i].in(),q[i].id=i;
	sort(q+1,q+m+1,cmp);
	update(a[1],1);
	for(int i=1;i<=m;i++){
		int ql=q[i].l,qr=q[i].r;
		while(l>ql) update(a[--l],1);
		while(r<qr) update(a[++r],1);
		while(l<ql) update(a[l++],-1);
		while(r>qr) update(a[r--],-1);
		ans[q[i].id]=query(q[i].a,q[i].b);
	}
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}