题目描述
有一排\(n\)棵树，第\(i\)棵树的高度是\(d_i\)。有一只鸟要从第\(1\)棵树飞到第\(n\)棵树。
如果鸟降落在第\(i\)棵树，那么它下一步可以降落到第\(i+1,i+2,\dots,i+k\)棵树之中的一棵。
如果鸟降落到一棵不矮于当前树的树，那么它的劳累值会\(+1\)，否则不会。
求劳累值的最小值。
输入
第一行一个正整数\(T(1\leq T\leq 2)\)，表示测试数据的数量。
每组数据第一行一个正整数\(n(2\leq n\leq 10^6)\)，表示树的数量。
第二行\(n\)个正整数\(d_1,d_2,\dots,d_n(1\leq d_i\leq 10^9)\)，表示每棵树的高度。
第三行一个正整数\(q(1\leq q\leq 25)\)，表示询问的数量。
接下来\(q\)行，每行一个正整数\(k(1\leq k\leq n-1)\)，表示一个询问。
输出
每组数据输出\(q\)行，每行一个整数，即在给定的\(k\)下劳累值的最小值。
样例输入 Copy
1
9
4 6 3 6 3 7 2 6 5
2
2
5
样例输出 Copy
2
1
check函数若从lambda改为bool会超时，加inline可以过
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
inline int log_2(int x) {return 31-__builtin_clz(x);}
inline int popcount(int x) {return __builtin_popcount(x);}
inline int lowbit(int x) {return x&-x;}
const int N = 1e6+10;
int q[N],d[N],f[N];
void solve()
{
//先考虑二维dp,用f[i]表示从1飞到i的劳累值最小值
//f[i] = min(f[j]+(d[j]<=d[i])) i-k<=j<=i-1
//考虑对于j<k
//若f[j]>f[k]的,k一定更优
//若f[j]<f[k],则j更优
//若f[j]==f[k],则d更高的优
int n;
cin>>n;
for(int i=1;i<=n;++i) cin>>d[i];
int Q;
cin>>Q;
while(Q--)
{
int k;
cin>>k;
//for(int i=1;i<=n;++i) cout<<d[i]<<" \n"[i==n];
int h = 1,t = 0;
auto check = [&](int j,int k)->bool
{
if(f[j] > f[k]) return true;
else if(f[j] < f[k]) return false;
else return d[k] >= d[j];
};
for(int i=1;i<=n;++i)
{
if(i >= k+1) while(h<=t&&q[h]<i-k) h++;
if(i==1) f[i] = 0;
else if(h<=t)
{
//注意取的是队首
f[i] = f[q[h]] + (d[q[h]]<=d[i]);
}
//在本题中应该先计算f[i]后更新单调队列
while(h<=t&&check(q[t],i)) t--;
q[++t] = i;
}
cout<<f[n]<<'\n';
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
cin>>T;
while(T--)
{
solve();
}
}