寒鸽儿のBlog

$f(x) = min\{a[k]\}, k \in [x-m+1, x]$

这显然是一个可以用优先队列优化的递推(dp)。
若 $i \leqslant j$ 且 $a[i] \geqslant a[j]$ 显然是无效的,优势只有数值更小或者下标更靠后(因为递推左边界在向右缩小)。
所以用单调队列维护即可。
$max$ 同理。
复杂度 $O(\mathcal{O(n)})$

#include <cstdio>
#include <queue>

using namespace std;

const int N = 1234567;
struct node{
	int x, v;
	node() {}
	node(int X, int V) :x(X), v(V) {}
};
deque<node> qmin, qmax;

int main() {
	int n, m, c, tmp, flg = 1;
	scanf("%d %d %d", &n, &m, &c);
	for(int i = 1; i <= m-1; ++i) {
		scanf("%d", &tmp);
		while(!qmin.empty()) {
			if(qmin.back().v >= tmp) qmin.pop_back();
			else break;
		}
		qmin.push_back(node(i, tmp));
		while(!qmax.empty()) {
			if(qmax.back().v <= tmp) qmax.pop_back();
			else break;
		}
		qmax.push_back(node(i, tmp));
	}
	for(int i = m; i <= n; ++i) {
		scanf("%d", &tmp);
		while(!qmin.empty()) {
			if(qmin.back().v >= tmp) qmin.pop_back();
			else break;
		}
		qmin.push_back(node(i, tmp));
		while(!qmax.empty()) {
			if(qmax.back().v <= tmp) qmax.pop_back();
			else break;
		}
		qmax.push_back(node(i, tmp)); 
		while(qmin.front().x < i-m+1) qmin.pop_front();
		while(qmax.front().x < i-m+1) qmax.pop_front();
		if(qmax.front().v - qmin.front().v <= c) {
			printf("%d\n", i-m+1);
			flg = 0;
		}
	}
	if(flg) {
		printf("NONE\n");
	}
	return 0;
}