再练下RMQ。。。多了个二分。。
话说为什么我的代码那么慢？(╯‵□′)╯︵┻━┻
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<iostream> 5 #include<cmath> 6 #include<queue> 7 #define inc(i,l,r) for(i=l;i<=r;i++) 8 #define dec(i,l,r) for(i=l;i>=r;i--) 9 #define inf 1e9 10 #define mem(a) memset(a,0,sizeof(a)) 11 #define ll long long 12 #define succ(x) (1<<x) 13 #define NM 50000+5 14 using namespace std; 15 int read(){ 16 int x=0,f=1;char ch=getchar(); 17 while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} 18 while(isdigit(ch))x=x*10+ch-'0',ch=getchar(); 19 return x*f; 20 } 21 int ans,n,i,a[NM],f[NM][25],d[NM][25],j,p; 22 int _max(int x,int y){ 23 return a[x]<a[y]?y:x; 24 } 25 int _min(int x,int y){ 26 return a[x]<a[y]?x:y; 27 } 28 int maxn(int l,int r){ 29 int k=log(r-l+1.0)/log(2.0); 30 return _max(d[l][k],d[r-succ(k)+1][k]); 31 } 32 int minn(int l,int r){ 33 int k=log(r-l+1.0)/log(2.0); 34 return _min(f[l][k],f[r-succ(k)+1][k]); 35 } 36 int erfen(int x,int l,int r){ 37 while(l<r){ 38 int t=l+r>>1; 39 if(x<a[minn(l,t)]) 40 l=t+1;else r=t; 41 } 42 return r; 43 } 44 int main(){ 45 while(~scanf("%d",&n)){ 46 ans=0; 47 inc(i,1,n)f[i][0]=d[i][0]=i,a[i]=read(); 48 p=log(n+1.0)/log(2.0); 49 inc(j,1,p) 50 for(i=1;i+succ(j-1)-1<=n;i++) 51 d[i][j]=_max(d[i][j-1],d[i+succ(j-1)][j-1]), 52 f[i][j]=_min(f[i][j-1],f[i+succ(j-1)][j-1]); 53 inc(i,1,n){ 54 j=erfen(a[i],i+1,n); 55 j=maxn(i,j); 56 ans=max(ans,j-i); 57 } 58 if(ans==0)ans=-1; 59 printf("%d ",ans); 60 } 61 return 0; 62 }