第一次写值域分块，然后 TLE 56分，感觉不像是常数的问题，又不像是复杂度的问题。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9,M = 1e5 + 9,SqrtN = 359;
int n,m;
int a[N],max_a; 
struct Block{
	struct block{
		int l,r;
		int val1,val2;
		//val1：该值域内有多少个数（可重复） 
		//val2：该值域内有多少个数（不重复） 
	} b[SqrtN];
	int block_len,block_cnt;
	int belong[N];
	void build_block(int len){
		block_len = block_cnt = sqrt(len);
		for(int i = 1;i <= block_cnt;i++){
			b[i].l = b[i - 1].r + 1;
			b[i].r = b[i].l + block_len - 1; 
		}
	}
} block1,block2;//block1：数列分块，block2：值域分块 
struct Query{
	int l,r,x,y;
	int id;
} q[M];
int ans1[M],ans2[M];
bool cmp(Query q1,Query q2){
	return (block1.belong[q1.l] ^ block1.belong[q1.l]) ? block1.belong[q1.l] < block1.belong[q1.l] : q1.r < q2.r;
}

int cnt[N];
void update(int v,int k){
	cnt[v] += k;
	block2.b[block2.belong[v]].val1 += k;
	block2.b[block2.belong[v]].val2 += ((k == 1 && cnt[v] == 1) || (k == -1 && cnt[v] == 0)) * k;
}

int query1(int l,int r){
	int pos_l = block2.belong[l],pos_r = block2.belong[l];
	int ret = 0;
	if(pos_l == pos_r){
		for(int i = l;i <= r;i++)
			ret += cnt[i];
		return ret;
	}
	for(int i = l;i <= block2.b[pos_l].r;i++)
		ret += cnt[i];
	for(int i = block2.b[pos_r].l;i <= r;i++)
		ret += cnt[i];
	for(int i = pos_l + 1;i <= pos_r - 1;i++)
		ret += block2.b[i].val1;
	return ret;
}
int query2(int l,int r){
	int pos_l = block2.belong[l],pos_r = block2.belong[l];
	int ret = 0;
	if(pos_l == pos_r){
		for(int i = l;i <= r;i++)
			ret += (cnt[i] >= 1);
		return ret;
	}
	for(int i = l;i <= block2.b[pos_l].r;i++)
		ret += (cnt[i] >= 1);
	for(int i = block2.b[pos_r].l;i <= r;i++)
		ret += (cnt[i] >= 1);
	for(int i = pos_l + 1;i <= pos_r - 1;i++)
		ret += block2.b[i].val2;
	return ret;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	block1.build_block(n);
	for(int i = 1;i <= n;i++){
		cin >> a[i];
		max_a = max(max_a,a[i]);
	}
	block2.build_block(max_a);
	for(int i = 1;i <= m;i++){
		cin >> q[i].l >> q[i].r >> q[i].x >> q[i].y;
		q[i].id = i;
	}
	sort(q + 1,q + m + 1,cmp);
	int lres = 1,rres = 0,tmp = 0;
    for(int i = 1;i <= m;i++){
        int L = q[i].l,R = q[i].r;
        int x = q[i].x,y = q[i].y;
        while(lres > L)
        	update(a[--lres],1);
        while(rres < R)
        	update(a[++rres],1);
        while(lres < L)
        	update(a[lres++],-1);
        while(rres > R)
        	update(a[rres--],-1);
        ans1[q[i].id] = query1(x,y);
        ans2[q[i].id] = query2(x,y);
    }
    for(int i = 1;i <= m;i++)
    	cout << ans1[i] << ' ' << ans2[i] << '\n';
	return 0;
}