P3572 [POI2014] PTA-Little Bird

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n, m, h[1000010], k[30], f[1000010], q[1000010], hh, tt;
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
	scanf("%d", &m);
	for (int i = 1; i <= m; i ++ ) scanf("%d", &k[i]);
	for (int t = 1; t <= m; t ++ ) {
		memset(f, 0x3f, sizeof f);
		f[1] = 0;
		memset(q, 0, sizeof q);
		hh = 1, tt = 0;
		q[ ++ tt] = 1;
		for (int i = 2; i <= n; i ++ ) {
			if (hh < i - k[t]) hh ++ ;
			f[i] = f[q[hh]] + (h[q[hh]] <= h[i]);
			while (hh <= tt && (f[q[tt]] > f[i] || (f[q[tt]] == f[i] && h[q[tt]] <= h[i]))) tt -- ;
			q[ ++ tt] = i;
		}
		printf("%d\n", f[n]);
	}
	return 0;
}