[AHOI2013]作业

题目描述

此时己是凌晨两点，刚刚做了 Codeforces 的小 A 掏出了英语试卷。英语作业其实不算多，一个小时刚好可以做完。然后是一个小时可以做完的数学作业，接下来是分别都是一个小时可以做完的化学，物理，语文……小 A 压力巨大。

这时小 A 碰见了一道非常恶心的数学题，给定了一个长度为 \(n\) 的数列和若干个询问，每个询问是关于数列的区间表示数列的第 \(l\) 个数到第 \(r\) 个数)，首先你要统计该区间内大于等于 \(a\)，小于等于 \(b\) 的数的个数，其次是所有大于等于 \(a\)，小于等于 \(b\) 的，且在该区间中出现过的数值的个数。

小 A 望着那数万的数据规模几乎绝望，只能向大神您求救，请您帮帮他吧。

输入格式

第一行两个整数 \(n,m\)

接下来 \(n\) 个不超过 \(10^5\) 的正整数表示数列

接下来 \(m\) 行，每行四个整数 \(l,r,a,b\)，具体含义参见题意。

输出格式

输出 \(m\) 行，分别对应每个询问，输出两个数，分别为在 \(l\) 到 \(r\) 这段区间中大小在 \([a,b]\) 中的数的个数，以及大于等于 \(a\)，小于等于 \(b\) 的，且在该区间中出现过的数值的个数（具体可以参考样例）。

样例 #1

样例输入 #1

样例输出 #1

提示

\(N\leq 100000,M\leq 100000\)，读入的数字均为 \([1,10^5]\) 内的正整数。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>

using namespace std;

int n, m, block, size_block, l = 1, r = 0;
int maxn;
int a[5211314], pos[5211314];
int cnt[5211314], size_add[5211314], size_cnt[5211314];
//此处的块指数的大小分成的块，而不是数的编号分成的块
//size_add表示在第i个块的数的个数 size_cnt指第i个块出现过的数值的个数
int out_cnt[5211314], out_sum[5211314];

struct ASK {
	int l, r, a, b, id;
}ask[5211314];

inline int read() {
	int 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 << 1) + (x << 3) + (ch - '0');
		ch = getchar();
	}
	return x * f;
}

inline bool cmp(ASK a, ASK b) {
	if (pos[a.l] != pos[b.l]) return pos[a.l] < pos[b.l];
	else return a.r < b.r;
}

inline void Add(int number) {
	cnt[number] ++;
	size_add[pos[number]] ++;
	if (cnt[number] == 1) {
		size_cnt[pos[number]] ++;
	}
	return;
}

inline void Del(int number) {
	cnt[number] --;
	size_add[pos[number]] --;
	if (cnt[number] == 0) {
		size_cnt[pos[number]] --;
	}
	return;
}

inline void GetAns(int minn, int maxn, int k) {
	int lift = pos[minn], right = pos[maxn];
	for (int i = minn; i <= min(lift * block, maxn); ++ i) {
		out_sum[k] += cnt[i];
		if (cnt[i] != 0) out_cnt[k] ++;
	}
	if (lift != right) {
		for (int i = (right - 1) * block + 1; i <= maxn; ++ i) {
			out_sum[k] += cnt[i];
			if (cnt[i] != 0) out_cnt[k] ++;
		}
	}
	for (int i = lift + 1; i <= right - 1; ++ i) {
		out_sum[k] += size_add[i];
		out_cnt[k] += size_cnt[i];
	}
}

int main() {
	n = read();
	m = read();
	block = sqrt(n);
	for (int i = 1; i <= n; ++ i) {
		a[i] = read();
		pos[i] = (i - 1) / block + 1;
		//pos[i]表示值i在第几个块
	}
	for (int i = 1; i <= m; ++ i) {
		ask[i].l = read();
		ask[i].r = read();
		ask[i].a = read();
		ask[i].b = read();
		ask[i].id = i;
	}
	stable_sort(ask + 1, ask + m + 1, cmp);
	for (int i = 1; i <= m; ++ i) {
		while (r < ask[i].r) Add(a[++ r]);	
		while (r > ask[i].r) Del(a[r --]);
		while (l > ask[i].l) Add(a[-- l]);
		while (l < ask[i].l) Del(a[l ++]);
		GetAns(ask[i].a, ask[i].b, ask[i].id);
	}
	for (int i = 1; i <= m; ++ i) {
		printf("%d %d\n", out_sum[i], out_cnt[i]);
	}
	return 0;
}