题解：CF2031D Penchick and Desert Rabbit

题意：i 可以跳到 j 当且仅当 j<i 且 a_j>a_i 或 j>i 且 a_j<a_i ，求每个 i 能跳到的最大 a_j。

做法：我们发现从一个点开始可能先往后再往前，顺序处理比较麻烦。我们考虑最开始可以较为简单求出答案的点，容易发现 a_i 最大的点往后的点肯定跳到这个点上。

我们的做法就出来了。每次求出答案未确定的点中 a_i 最大的点。如果它能跳到 j 且 j 的答案已求出，答案 ans_i=ans_j (我们是从大往小枚举，先求出的答案肯定大)。 再让它后面所有没求出答案的 j 答案为 ans_i 。

    #include<bits/stdc++.h>
    using namespace std;
    const int N=5e5+10;
    int n,a[N],c[N],ans[N],mn[N];
    bool cmp(int aa,int b) {
        return a[aa]>a[b];
    }
    void solve() {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
           scanf("%d",&a[i]);
        mn[n+1]=1e9;
        for(int i=n;i>=1;i--) 
            c[i]=i,mn[i]=min(mn[i+1],a[i]);
        sort(c+1,c+n+1,cmp);
        int id=c[1];
        for(int i=c[1];i<=n;i++) ans[i]=a[id];
        for(int i=2;i<=n;i++) {
            if(c[i]>id) continue ;
            if(a[c[i]]>mn[id]) ans[c[i]]=ans[id];
            else ans[c[i]]=a[c[i]];
            for(int j=c[i];j<id;j++) ans[j]=ans[c[i]];
            id=c[i];
        }
        for(int i=1;i<=n;i++) printf("%d ",ans[i]);
        printf("\n");
    }
    signed main() {
        int t;
        cin>>t;
        while(t--) solve();
        return 0;
    }