MnZn刚学莫队在线求助

#include<bits/stdc++.h>

namespace IO {
	inline int read() {
		int ret = 0, f = 1;char ch = getchar();
		while (ch < '0' || ch > '9') {
			if (ch == '-')  f = -f;
			ch = getchar();
		}
		while (ch >= '0' && ch <= '9') {
			ret = (ret << 1) + (ret << 3) + (ch ^ 48);
			ch = getchar();
		}
		return ret * f;
	}
	void write(int x) {
		if (x < 0) putchar('-'), x = -x;
		if (x > 9) write(x / 10);
		putchar(x % 10 + '0');
	}
}

using namespace IO;
using namespace std;

const int maxn = 1e5 + 5;

int n, m, Max;
int L[maxn], R[maxn], f[maxn];
pair<int, int> Ans[maxn];
struct Node {
	int l, r, a, b, id;
	bool operator == (const Node & x) const {
		return x.l == l && x.r == r && x.a == a && x.b == b;
	}
};
int a[maxn], sum[maxn], s[maxn], num[maxn], len;
Node q[maxn];

bool cmp(Node a, Node b) {
	int fa = (a.l - 1) / len + 1, fb = (b.l - 1) / len + 1;
	return fa == fb ? a.r < b.r : a.l < b.l;
}

void init() {
	int x = sqrt(Max);
	for (int i = 1;i <= x;i++) {
		L[i] = (i - 1) * x + 1;
		R[i] = i * x;
		for (int j = L[i];j <= R[i];j++) f[j] = i;
	}
	if (R[x] != n) {
		L[++x] = R[x - 1] + 1;
		R[x] = n;
		for (int i = L[x];i <= R[x];i++) f[i] = x;
	}
}

void add(int x) {
	if (a[s[x]] == 0) num[f[s[x]]]++;
	a[s[x]]++, sum[f[s[x]]]++;
}

void del(int x) {
	if (a[s[x]] == 1) num[f[s[x]]]--;
	a[s[x]]--, sum[f[s[x]]]--;
}

pair<int, int> query(int l, int r) {
	r = min(r, Max);
	int lk = f[l], rk = f[r];
	pair<int, int> cnt;cnt.first = 0, cnt.second = 0;
	
	if (lk == rk) {
		for (int i = l;i <= r;i++) {
			cnt.second += (a[i] > 0);
			cnt.first += a[i];
		}
		return cnt;
	}
	
	for (int i = l;i <= R[lk];i++) {
		cnt.second += (a[i] > 0);
		cnt.first += a[i];
	}
	for (int i = lk + 1;i < rk;i++) cnt.first += sum[i], cnt.second += num[i];
	for (int i = L[rk];i <= r;i++) {
		cnt.second += (a[i] > 0);
		cnt.first += a[i];
	}
	
	return cnt;
}

int main() {
	n = read(), m = read();len = sqrt(m);
	for (int i = 1;i <= n;i++) s[i] = read(), Max = max(Max, s[i]);
	for (int i = 1;i <= m;i++) q[i].l = read(), q[i].r = read(), q[i].a = read(), q[i].b = read(), q[i].id = i;

	sort(q + 1, q + 1 + m, cmp);
	
	for (int i = 1, l = 1, r = 0;i <= m;i++) {
		if (q[i] == q[i - 1]) {
			Ans[q[i].id] = Ans[q[i - 1].id];
			continue;
		}
		while (l > q[i].l) add(--l);
		while (r < q[i].r) add(++r);
		while (l < q[i].l) del(l++);
		while (r > q[i].r) del(r--);
		Ans[q[i].id] = query(q[i].a, q[i].b);
	}
	
	for (int i = 1;i <= m;i++) write(Ans[i].first), putchar(' '), write(Ans[i].second), putchar(10);
	
	return 0;
}