记录编号	576289	评测结果	AAAAAAATTT
题目名称	[AHOI 2013] 作业	最终得分	70
用户昵称	Lfc_HeSn	是否通过	未通过
代码语言	C++	运行时间	3.865 s
提交时间	2022-10-06 17:53:34	内存使用	0.00 MiB

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1000010;
int n, m, s, a[MAXN], b[MAXN], c[MAXN], d[MAXN], ans1[MAXN], ans2[MAXN];
struct node {
	int l, r, x, y, id;
}q[MAXN];
bool cmp(node x, node y) {
	if(x.l / s != y.l / s) {
		return x.l / s < y.l / s;
	}
	return x.r / s < y.r / s;
}
void add(int x) {
	++ b[a[x]];
	d[a[x] / s] ++;
	if(b[a[x]] == 1) {
		c[a[x] / s] ++;
	}
}
void del(int x) {
	-- b[a[x]];
	d[a[x] / s] --;
	if(!b[a[x]]) {
		c[a[x] / s] --;
	}
}
int query1(int x, int y) {
	int ka = x / s, kb = y / s;
	if(ka == kb) {
		int sum = 0;
		for(int i = x; i <= y; i ++) {
			sum += b[i];
		}
		return sum;
	}
	int sum = 0;
	sum += query1(x, (ka + 1) * s - 1);
	sum += query1(kb * s, y);
	for(int i = ka + 1; i < kb; i ++) {
		sum += d[i];
	}
	return sum;
}
int query2(int x, int y) {
	int ka = x / s, kb = y / s;
	if(ka == kb) {
		int sum = 0;
		map<int, int> mp;
		for(int i = x; i <= y; i ++) {
			if(b[i] && !mp[i]) {
				mp[i] = 1;
				sum ++;
			}
		}
		return sum;
	}
	int sum = 0;
	sum += query2(x, (ka + 1) * s - 1);
	sum += query2(kb * s, y);
	for(int i = ka + 1; i < kb; i ++) {
		sum += c[i];
	}
	return sum;
}
signed main() {
	freopen("ahoi2013_homework.in", "r", stdin);
	freopen("ahoi2013_homework.out", "w", stdout);
	cin >> n >> m;
	s = sqrt(n);
	for(int i = 1; i <= n; i ++) {
		cin >> a[i];
	}
	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 l = q[1].l, r = q[1].l - 1;
	for(int i = 1; i <= m; i ++) {
		while(l < q[i].l) {
			del(l ++);
		}
		while(l > q[i].l) {
			add(-- l);
		}
		while(r < q[i].r) {
			add(++ r);
		}
		while(r > q[i].r) {
			del(r --);
		}
		ans1[q[i].id] = query1(q[i].x, q[i].y);
		ans2[q[i].id] = query2(q[i].x, q[i].y);
	}
	for(int i = 1; i <= m; i ++) {
		cout << ans1[i] << ' ' << ans2[i] << endl;
	}
	return 0;
}