音量问题 / Sound 静音问题

题目链接：ybt金牌导航1-3-4 / luogu P4392

题目大意

给你一些数，然后问你有多少个长度为 m 的区间满足区间最大减区间最小小于等于一个给定的值。
输出所有满足条件的区间的起始位置，如果没有满足的就输出 NONE。

思路

看到题目一开始想到了类似线段树 / 树状数组的东西，不过发现如果是 $10^7$ 的数据过不了。

然后就想到把它分解成求最大和求最小，然后你会发现它求的区间长度相同。
那就变成了滑动窗口，然后就单调队列做就可以了。

代码

#include<cstdio>

using namespace std;

int n, m, c, a[10000001], head;
int maxn[10000001], minn[10000001];
int sta[10000001], num[10000001];
bool yes;

int read() {//由于读入量有点大用个快读（不知道不用会不会超时）
	char c = getchar();
	int re = 0, zf = 1;
	while (c < '0' || c > '9') {
		zf = -zf;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		re = (re << 3) + (re << 1) + c - '0';
		c = getchar();
	}
	return re * zf;
}

int main() {
	n = read();
	m = read();
	c = read();
	for (int i = 1; i <= n; i++) a[i] = read();
	
	head = 1;
	for (int i = 1; i <= n; i++) {//单调队列求区间最大
		while (sta[0] >= head && a[i] >= sta[sta[0]]) sta[0]--;
		sta[++sta[0]] = a[i];
		num[sta[0]] = i;
		if (i >= m) {
			maxn[i - m + 1] = sta[head];
			if (num[head] == i - m + 1) head++;
		}
	}
	head = 1;
	sta[0] = 0;
	for (int i = 1; i <= n; i++) {//单调队列求区间最小
		while (sta[0] >= head && a[i] <= sta[sta[0]]) sta[0]--;
		sta[++sta[0]] = a[i];
		num[sta[0]] = i;
		if (i >= m) {
			minn[i - m + 1] = sta[head];
			if (num[head] == i - m + 1) head++;
		}
	}
	
	for (int i = 1; i + m - 1 <= n; i++)
		if (maxn[i] - minn[i] <= c) {
			yes = 1;
			printf("%d\n", i);
		}
	if (!yes) printf("NONE");
	
	return 0;
}