思路仿照带修莫队，多加了两个对于值域的指针。代码在没有奇偶性排序时过不了，块长为 $sqrt(n)$ 时过不了，为 $n^{ \frac{2}{3} }$ 时可以过，如果不是因为数据问题而过了，求算法复杂度分析（码风微抽象

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

const int N=1e5+5;
int n,m,a[N],len,b[N],ans[2][N];
struct node{ int l,r,a,b,id; }t[N];
int cmp(node x,node y){ return b[x.l]==b[y.l]?(b[x.r]==b[y.r]?(b[x.a]==b[y.a]?(b[x.a]&1?x.b<y.b:x.b>y.b):b[x.r]&1?x.a<y.a:x.a>y.a):b[x.l]&1?x.r<y.r:x.r>y.r):x.l<y.l; }
int l=1,r,x=1,y,cnt,dcnt,c[N];
void add(int u){ c[u]++,cnt+=(x<=u&&u<=y),dcnt+=(x<=u&&u<=y&&c[u]==1); }
void del(int u){ dcnt-=(x<=u&&u<=y&&c[u]==1),cnt-=(x<=u&&u<=y),c[u]--; }
void Add(int u){ cnt+=c[u],dcnt+=!!c[u]; }
void Del(int u){ cnt-=c[u],dcnt-=!!c[u]; }
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",a+i);
	for(int i=1;i<=m;i++)
		scanf("%d%d%d%d",&t[i].l,&t[i].r,&t[i].a,&t[i].b),t[i].id=i;
	len=pow(n,2./3);
	for(int i=1;i<=n;i++)
		b[i]=(i-1)/len+1;
	sort(t+1,t+1+m,cmp);
	for(int i=1;i<=m;i++){
		int u=t[i].l,v=t[i].r,p=t[i].a,q=t[i].b;
		while(l>u) add(a[--l]);
		while(r<v) add(a[++r]);
		while(x>p) Add(--x);
		while(y<q) Add(++y);
		while(x<p) Del(x++);
		while(y>q) Del(y--);
		while(l<u) del(a[l++]);
		while(r>v) del(a[r--]);
		ans[0][t[i].id]=cnt,ans[1][t[i].id]=dcnt;
	}
	for(int i=1;i<=m;i++)
		printf("%d %d\n",ans[0][i],ans[1][i]);
	
	return 0;
}