TLE on #13, 1.20s.

玄关。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using pii=pair<int,int>;
#define fi first
#define se second
#ifdef ONLINE_JUDGE
	#define getchar getchar_unlocked
	#define putchar putchar_unlocked
#endif
template<typename Tp> Tp read() {
	Tp x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
template<typename Tp> void write(Tp x) {
	if(x<0) {putchar('-');x=-x;}
	static int sta[45];int top=0;
	do {sta[top++]=x%10;x/=10;} while(x);
	while(top) putchar(sta[--top]+'0');
}
constexpr int N=1e5+5;
int n,m,a[N],block;
pii ans[N];
struct Query {
	int id,l,r,x,y;
} que[N];
bool cmp(const Query &A,const Query &B) {
	int posA=A.l/block,posB=B.l/block;
	if(posA!=posB) return posA<posB;
	if(posA&1) return A.r<B.r;
	else return A.r>B.r;
}
struct node {
	int l,r,sum,num;
} tr[N<<2];
inline int ls(int p) {return p<<1;}
inline int rs(int p) {return p<<1|1;}
inline void pushup(int p) {
	tr[p].sum=tr[ls(p)].sum+tr[rs(p)].sum;
	tr[p].num=tr[ls(p)].num+tr[rs(p)].num;
}
void build(int p,int l,int r) {
	tr[p].l=l,tr[p].r=r;
	if(l==r) return;
	int mid=(l+r)>>1;
	build(ls(p),l,mid);
	build(rs(p),mid+1,r);
}
void update(int p,int x,int d) {
	if(tr[p].l==tr[p].r) {
		tr[p].sum+=d;
		if(d==1&&tr[p].sum==1) tr[p].num=1;
		else if(d==-1&&tr[p].sum==0) tr[p].num=0;
		return;
	}
	int mid=(tr[p].l+tr[p].r)>>1;
	if(x<=mid) update(ls(p),x,d);
	else update(rs(p),x,d);
	pushup(p);
}
int query1(int p,int l,int r) {
	if(l<=tr[p].l&&r>=tr[p].r) return tr[p].sum;
	int mid=(tr[p].l+tr[p].r)>>1,res=0;
	if(l<=mid) res+=query1(ls(p),l,r);
	if(r>mid) res+=query1(rs(p),l,r);
	return res;
}
int query2(int p,int l,int r) {
	if(l<=tr[p].l&&r>=tr[p].r) return tr[p].num;
	int mid=(tr[p].l+tr[p].r)>>1,res=0;
	if(l<=mid) res+=query2(ls(p),l,r);
	if(r>mid) res+=query2(rs(p),l,r);
	return res;
}
inline void add(int x) {update(1,a[x],1);}
inline void del(int x) {update(1,a[x],-1);}
int main() {
	// ios::sync_with_stdio(false);
	// cin.tie(0);cout.tie(0);
	// cin>>n>>m;
	n=read<int>(),m=read<int>();
	block=sqrt(n);
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++) {
		que[i].id=i;
		// cin>>que[i].l>>que[i].r>>que[i].x>>que[i].y;
		que[i].l=read<int>(),que[i].r=read<int>(),que[i].x=read<int>(),que[i].y=read<int>();
	}
	sort(que+1,que+m+1,cmp);
	build(1,1,100000);
	int l=1,r=0;
	for(int i=1;i<=m;i++) {
		while(l>que[i].l) add(--l);
		while(r<que[i].r) add(++r);
		while(l<que[i].l) del(l++);
		while(r>que[i].r) del(r--);
		ans[que[i].id]={query1(1,que[i].x,que[i].y),query2(1,que[i].x,que[i].y)};
	}
	for(int i=1;i<=m;i++) {
		// cout<<ans[i].fi<<" "<<ans[i].se<<"\n";
		write<int>(ans[i].fi);
		putchar(' ');
		write<int>(ans[i].se);
		putchar('\n');
	}
	return 0;
}