可以先处理出每个a[i]最左和最右能到达的位置，L[i]，和R[i]。然后就只要询问区间[ L[i],i-1 ]和区间[ i+1,R[i] ]最大值位置即可。
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<iostream> using namespace std; typedef long long LL; const double pi=acos(-1.0),eps=1e-8; void File() { freopen("D:\in.txt","r",stdin); freopen("D:\out.txt","w",stdout); } inline int read() { char c = getchar(); while(!isdigit(c)) c = getchar(); int x = 0; while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } return x; } const int maxn=50000+10; int T,n,a[maxn],L[maxn],R[maxn],dp[maxn][30]; void RMQ_init() { for(int i=0;i<n;i++) dp[i][0]=i; for(int j=1;(1<<j)<=n;j++) for(int i=0;i+(1<<j)-1<n;i++) { if(a[dp[i][j-1]]>a[dp[i+(1<<(j-1))][j-1]]) dp[i][j]=dp[i][j-1]; else dp[i][j]=dp[i+(1<<(j-1))][j-1]; } } int RMQ(int L,int R) { int k=0; while((1<<(k+1))<=R-L+1) k++; if(a[dp[L][k]]>a[dp[R-(1<<k)+1][k]]) return dp[L][k]; return dp[R-(1<<k)+1][k]; } int main() { scanf("%d",&T); int cas=1; while(T--) { scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&a[i]), L[i]=R[i]=i; for(int i=1;i<n;i++) { if(a[i]<a[i-1]) continue; int pre=L[i-1]; while(1) { L[i]=pre; if(pre==0||a[pre-1]>a[i]) break; pre=L[pre-1]; } } for(int i=n;i>=1;i--) R[i]=i; for(int i=n-2;i>=0;i--) { if(a[i]<a[i+1]) continue; int pre=R[i+1]; while(1) { R[i]=pre; if(pre==n-1||a[pre+1]>a[i]) break; pre=R[pre+1]; } } RMQ_init(); printf("Case %d: ",cas++); for(int i=0;i<n;i++) { if(L[i]>i-1) printf("0 "); else printf("%d ",RMQ(L[i],i-1)+1); if(R[i]<i+1) printf("0 "); else printf("%d ",RMQ(i+1,R[i])+1); } } return 0; }