小红越级(easy)

链接

虽然是简单版本,但也不太好写,主要还是时间问题上

对于这题不舒适度的情况,我们需要分三类讨论

1.x太大,导致一些曲子难度高的版本都偏低

2.x太小,与1相反

3.曲子难度差距太大,导致x在中间而产生不舒适度

对于情况一,我们需要计算有多少曲子的高难小于x-2,记为a

对于情况二,我们需要计算有多少曲子的低难高于x+1,记为b

对于请况三,我们需要计算有多少曲子高低难度差别太大,记为c

由于这三种情况互斥而且刚好等于所有不舒适度的情况,因此总不舒适度为a+b+c

对于a,我们只需要求前缀和即可,对于b我们可以反着求,先求前缀和,在计算n-b1(b1是前缀和),对于c,也可以用前缀和的思想,在低难+2处加一,高难减一处减一,这样就可以控制什么时候加,什么时候停。比如1 8 ,3 处加一,7处减一,这样前缀和就是3-6都是1,7以后都是0

完整思路在这,可以写代码了

#include<iostream>
using namespace std;
#define MAX 200005
int n;
int a[MAX], b[MAX], pre_a[MAX], pre_b[MAX], diff[MAX];
void f() {
	fill(pre_a, pre_a + n+2, 0);//索引从1开始,赋值尽量多一点
	fill(pre_b, pre_b + n+2, 0);
	fill(diff, diff + n + 2, 0);
	int q;
	cin >> n;
	cin >> q;
	for (int i = 1;i <= n;i++) {
		cin >> a[i] >> b[i];
		pre_a[a[i]]++;//存储最小值,即低难
		pre_b[b[i]]++;//存储最大值,即高难
					
	}
	for (int i = 1;i <= n;i++) {
		pre_a[i] += pre_a[i - 1];
		pre_b[i] += pre_b[i - 1];

		if (a[i] + 2 <= b[i] - 2) {//中间出现缺口
			diff[a[i] + 2]++;
			diff[b[i] - 1]--;
		}
	}

	for (int i = 1;i <= n;i++) {
		diff[i] += diff[i - 1];
	}

	while (q--) {
		int x;
		cin >> x;

		//x偏大,但是可能x-2小于0,不过这只需要另外讨论即可
		int a = x - 2 >= 0 ? pre_b[x - 2] : 0;//有多少组的最大值不大于x-2,如果x-2小于0,就没有一组满足了,也就是0

		//x偏小,但是x+1可能超过了n,一样记为0就好
		int b = x + 1 <= n ? n - pre_a[x + 1] : 0;//有多少组最小值不大于x+1,但我们需要大于x+1的,所以用n减去

		//中间情况
		int c = diff[x];

		int sum = a + b + c;
		cout << sum << " ";
	}
	cout << endl;
}
int main() {
	int T;
	cin >> T;
	while (T--) {
		f();
	}
}

时间复杂度:O(T x (n+q))

空间复杂度:O(n)