Solution

题目要求每个位置能跳到的最高高度，而由跳跃操作的条件可知往前跳是一定会变高的，往后跳是一定会变矮的。所以思考为啥会往后跳？肯定是当前位置到后一个比它矮的位置中间有比它高的才会往后跳去取到那个更高的位置。

设 dp_i 为 i 能跳到的最大高度，v_i=\displaystyle\max_{j=1}^i a_j（即前缀最大值）。因为可以一直往前跳，初始化 dp_i=v_i。从后往前扫，有转移：dp_i\gets\displaystyle\max_{i<j,a_j<v_i}dp_j，就是说可以从前缀最大值那个地方往后跳到一个比它低的位置。很明显的二维偏序关系，以 a 为下标放在树状数组上，可以优化至 O(n\log n)。

Code

#include<bits/stdc++.h>
inline int lowbit(int x){
    return x&-x;
}
int t[500005];
int n;
inline void add(int x,int y){
    for(;x<=n;x+=lowbit(x))t[x]=std::max(t[x],y);
}
inline int ask(int x){
    static int s;s=0;
    for(;x;x^=lowbit(x))s=std::max(s,t[x]);
    return s;
}
int dp[500005];
int a[500005];
int T;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;++i)
            scanf("%d",&a[i]),dp[i]=std::max(dp[i-1],a[i]),t[i]=0;
        for(int i=n;i;--i)
            add(a[i],dp[i]=std::max(dp[i],ask(dp[i]-1)));
        for(int i=1;i<=n;++i)
            printf("%d%c",dp[i]," \n"[i==n]);
    }
    return 0;
}