本文共 1167 字，大约阅读时间需要 3 分钟。
可以先处理出每个a[i]最左和最右能到达的位置，L[i]，和R[i]。然后就只要询问区间[ L[i],i-1 ]和区间[ i+1,R[i] ]最大值位置即可。
#include #include #include #include #include #include #include #include #include #include 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 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< 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]) break; pre=R[pre+1]; } } RMQ_init(); printf("Case %d:\n",cas++); for(int i=0;i i-1) printf("0 "); else printf("%d ",RMQ(L[i],i-1)+1); if(R[i]
转载于:https://www.cnblogs.com/zufezzt/p/5740703.html