CUGBACM Codeforces Tranning 3 题解 - c++编程基础

找到起点终点之间的最高高度和最低高度，如果符合条件，那么终点右移，否则终点左移。查询最高高度和最低高度的方式是ST表，O(NlogN)的预处理，然后O(1)的查询，二分的过程中的复杂度也是O(NlogN)。

代码：

#include 
                   
                    
#include 
                    
                      #include 
                     
                       #include 
                      
                        #include 
                       
                         #include 
                        
                          #include 
                         
                           #include 
                          
                            #include
                            #include 
                            
                              #include 
                             
                               #include 
                              
                                #include 
                               
                                 #include 
                                
                                  #define eps 1e-8 #define INF 0x7fffffff #define maxn 100005 #define PI acos(-1.0) #define seed 31//131,1313 #define LOCAL typedef long long LL; typedef unsigned long long ULL; using namespace std; int stTable_min[maxn][32],stTable_max[maxn][32]; int preLog2[maxn]; int h[maxn]; int Left[maxn],Right[maxn]; int ans = 0,times = 0; void st_prepare(int n,int *array) { preLog2[1]=0; for(int i=2; i<=n; i++) { preLog2[i]=preLog2[i-1]; if((1<
                                 
                                  =0; i--) { stTable_min[i][0]=array[i]; stTable_max[i][0]=array[i]; for(int j=1; (i+(1<
                                  
                                   l+1) { int mid = (l + r) / 2; if(query_sub(i,mid)>k) r=mid; else l=mid; } if(l-i+1>ans) { ans=l-i+1; times=1; Left[0]=i; Right[0]=l; } else if(l-i+1==ans) { Left[times]=i; Right[times++]=l; } } printf(%d %d ,ans,times); for(int i=0;i
                                   
                                    ?






                                    ?

CUGBACM Codeforces Tranning 3 题解(二)