具体是莫队+树状数组。

#include <bits/stdc++.h>
#define N 100005
using namespace std;

inline int read() {
	int res = 0, f = 1; char c = getchar();
	while (c < '0' || c > '9') c = getchar();
	while ('0' <= c && c <= '9') { res = (res << 1) + (res << 3) + (c ^ 48); c = getchar(); }
	return res;
}
int n, m, a[N], bel[N];
int sz, tr1[N << 2], cnt[N], ap[N], tr2[N << 2];
int ans1[N], ans2[N];
int l = 1, r = 0, L, R;
struct node {
	int l, r;
	int a, b;
	int id;
} q[N];

inline bool cmp(node x, node y) { return (bel[x.l] == bel[y.l]) ? ((bel[x.l] & 1) ? x.r < y.r : x.r > y.r) : bel[x.l] < bel[y.l]; }

inline void upd1(int x, int v) { for (; x <= n; x += (x & -x)) tr1[x] += v; }
inline int sum1(int x) { int res = 0; for (; x; x -= (x & -x)) res += tr1[x]; return res; }
inline void upd2(int x, int v) { for (; x <= n; x += (x & -x)) tr2[x] += v; }
inline int sum2(int x) { int res = 0; for (; x; x -= (x & -x)) res += tr2[x]; return res; }

inline void del(int x) {
	cnt[x]--;
	if (cnt[x] == 0) upd2(x, -1);
	upd1(x, -1);
}
inline void add(int x) {
	cnt[x]++;
	if (cnt[x] == 1) upd2(x, 1);
	upd1(x, 1);
}

int main() {
//	freopen("P4396_8.in", "r", stdin);
//	freopen("P4396_8.ans", "w", stdout);
	n = read(), m = read();
	sz = sqrt(max(n, m));
	for (int i = 1; i <= n; ++i) a[i] = read(), bel[i] = (i - 1) / sz + 1;
	for (int i = 1; i <= m; ++i) q[i].l = read(), q[i].r = read(), q[i].a = read() - 1, q[i].b = read(), q[i].id = i;
	sort(q + 1, q + 1 + n, cmp);
	for (int i = 1; i <= m; ++i) {
		L = q[i].l, R = q[i].r;
		while (l < L) del(a[l++]);
		while (l > L) add(a[--l]);
		while (r < R) add(a[++r]);
		while (r > R) del(a[r--]);
		ans1[q[i].id] = sum1(q[i].b) - sum1(q[i].a);
		ans2[q[i].id] = sum2(q[i].b) - sum2(q[i].a);
	}
	for (int i = 1; i <= m; ++i) cout << ans1[i] << ' ' << ans2[i] << '\n';
	return 0;
}