一血yeah yeah。
第一眼觉得是比较麻烦的单调队列。
然后发现转移的时候只会加1或者不加。
那么取的时候只用取队首，队里首先fi单不降然后hi单减。那么一定没有方案比取队首差。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
int _d_;
#define readInt(_x_) { \
int& _s_ = (_x_ = 0); \
while (!isdigit(_d_ = getchar())); \
while (_s_ = _s_ * 10 + _d_ - 48, isdigit(_d_ = getchar())); \
}
const int maxn = 1000009;
int n, m, a[maxn], f[maxn], q[maxn];
int getTrans(int l, int r) {
int v0 = f[q[l]];
while (l < r) {
int mid = (l + r + 1) >> 1;
if (f[q[mid]] == v0)
l = mid;
else
r = mid - 1;
}
return q[l];
}
int dp(int l) {
int hd = 0, tl = 1;
f[1] = 0;
q[0] = 1;
for (int i = 2; i <= n; ++ i) {
while (i - q[hd] > l)
++ hd;
int j = q[hd];
f[i] = f[j] + (a[i] >= a[j]);
while (hd < tl && (f[i] < f[q[tl - 1]] || (f[i] == f[q[tl - 1]] && a[i] >= a[q[tl - 1]])))
-- tl;
q[tl ++] = i;
}
return f[n];
}
int main() {
#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
#endif
readInt(n);
for (int i = 1; i <= n; ++ i)
readInt(a[i]);
readInt(m);
while (m --) {
int k;
readInt(k);
printf("%d\n", dp(k));
}
}