代码思路和第一篇类似，但是运行速度在数据增大时变得很慢。
另外问一句，我们老师把这道题M开到了1e6，时限10s，我在做对拍的时候发现好多题解都达不到，请问有没有一种基于莫队更好的方法？

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1e5+10,maxm=1e6+10,sqmaxn=400;//fn:fknum  ans:1:large;0:small
int N,sqn,M,a[maxn],ls[maxn],lstop=0,f[maxn],fn[sqmaxn][2],ul,ur,ans[maxm][2];
struct node{int l,r,_x,_y,id;}q[maxm];
int qd(){
	int rt=0;char c=getchar();
	while(c<'0'||c>'9')  c=getchar();
	while('0'<=c&&c<='9')  rt=(rt<<3)+(rt<<1)+c-48,c=getchar();
	return rt;
}
bool cmp(const node &x,const node &y){
	if(x.l/sqn==y.l/sqn)  return x.r<y.r;
	return x.l<y.l;
}
void change(int p,int v){
	int _p=p/sqn;
	f[p]+=v;fn[_p][1]+=v;
	if(a[p]==0)  fn[_p][0]--;
	else if(a[p]==v)  fn[_p][0]++;
//	printf("upd f%d(%d)=%d\n",p,ls[p],f[p]);
	return;
}
void ask(int l,int r,int p){
	int _l=lower_bound(ls+1,ls+lstop+1,l)-ls,_r=lower_bound(ls+1,ls+lstop+1,r)-ls;
	if(ls[_r]!=r)  _r--;
	l=_l,r=_r;
//	printf("l'=%d r'=%d\n",l,r);
	if(r-l<=sqn*2){
		for(int i=l;i<=r;i++)  ans[p][1]+=f[i],ans[p][0]+=(f[i]?1:0);
		return;
	}
//	printf("_l=%d _r=%d\n",_l,_r );
	_l=l/sqn+(l%sqn?1:0),_r=r/sqn-((r+1)%sqn?1:0);
	for(int i=l;i<_l;i++)  ans[p][1]+=f[i],ans[p][0]+=(f[i]?1:0);
	for(int i=_l;i<=_r;i++)  ans[p][1]+=fn[i][1],ans[p][0]+=fn[i][0];
	for(int i=_r*sqn+_r;i<=r;i++)  ans[p][1]+=f[i],ans[p][0]+=(f[i]?1:0);
	return;
}
int main(){
	N=qd(),M=qd();sqn=pow(1.0*N*M,0.25);sqn=N;
	for(int i=1;i<=N;i++)  a[i]=ls[i]=qd();
	sort(ls+1,ls+N+1);
	lstop=unique(ls+1,ls+N+1)-ls-1;
	for(int i=1;i<=N;i++)  a[i]=lower_bound(ls+1,ls+lstop+1,a[i])-ls;
	for(int i=1;i<=M;i++)  q[i].l=qd(),q[i].r=qd(),q[i]._x=qd(),q[i]._y=qd(),q[i].id=i;
	sort(q+1,q+M+1,cmp);
	for(int i=q[1].l;i<=q[1].r;i++)  change(a[i],1);
	ul=q[1].l,ur=q[1].r;ask(q[1]._x,q[1]._y,q[1].id);
	for(int i=2;i<=M;i++){
		while(ul<q[i].l)  change(a[ul++],-1);
		while(ur>q[i].r)  change(a[ur--],-1);
		while(ul>q[i].l)  change(a[--ul],1);
		while(ur<q[i].r)  change(a[++ur],1);
//		printf("ask %d %d %d %d %d\n",q[i].l,q[i].r,q[i]._x,q[i]._y,q[i].id);
		ask(q[i]._x,q[i]._y,q[i].id);
	}
	for(int i=1;i<=M;i++)  printf("%d %d\n",ans[i][1],ans[i][0]);
	return 0;
}