BUAA 752 （2013北航校赛B）

链接：http://acm.buaa.edu.cn/problem/752/

这题在北航就一直卡着，卡到结束后第二天交了一发发现T了，太逗了。

题意是求"长度一定的连续字串中的最大值"的最小值。

思路没什么问题，用两个数组分别记录每个点左端第一个比本身值大的端点LE和右端第一个比本身值大的端点RI，然后RI-LE-1即为长度，是O(NlogN）。

T的原因在于每次询问的时候都用了O(N)的查询，这样时间复杂度就达到了O(M*N)。

应该建立一个数组记录每个长度的对应最小值，O(N) 的更新操作，查询时复杂度是O(1)。

代码

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #define pi acos(-1.0) #define INF 1<<25 #define maxn 100005 using namespace std; typedef long long ll; ll num [maxn]; int le[maxn]; int ri[maxn]; int cc[maxn]; ll ans[maxn]; int main() { int tot,lim; scanf("%d",&tot); for(int ii=0; ii
            
             =0) le[i]=le[le[i]]; } for(int i=tt-1; i>=0; i--) { ri[i]=i+1; while(num[ri[i]]<=num[i]&&ri[i]<=tt-1) ri[i]=ri[ri[i]]; cc[i]=ri[i]-le[i]-1; } memset(ans,-1,sizeof(ans)); for(int i=0;i
             
              num[i]) ans[cc[i]]=num[i]; } for(int i=tt-1;i>=1;i--) { if(ans[i+1]==-1) continue; else if(ans[i]==-1) ans[i]=ans[i+1]; else ans[i]=min(ans[i],ans[i+1]); } int tt2; scanf("%d",&tt2); for(int i=0; i