一看就是十分简单的题 , 然后上去开始无脑程序

超时~~~ 感觉时间复杂度 , 已经很低了 , 但是并没有什么卵用 .

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
              10 #include
              
               11 #include
               
                12 #include
                13 #include
                 
                  14 #include
                  
                   15 using namespace std;16 int main()17 {18 int w,q,a[100000],n,m;19 scanf("%d%d",&w,&q);20 for(int i=1;i<=w;i++)21 scanf("%d",&a[i]);22 for(int i=0;i
                   
                    a[j]?maxn:a[j];29 minn=minn

两个程序的时间复杂度

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
              10 #include
              
               11 #include
               
                12 #include
                13 #include
                 
                  14 #include
                  
                   15 using namespace std;16 int dp_max[100005][17];17 int dp_min[100005][17];18 void RMQ(int n)19 {20 for(int j = 1; j < 17; j++) // 这里 为啥 是 20 呢 ? //F[i, j]表示从第i个数起连续2^j个数中的最大值。（DP的状态） ???21 {22 for(int i = 1; i <= n; i++) 23 {24 if( i + (1<
                   
                    <= n)25 {26 dp_max[i][j] = max(dp_max[i][j-1],dp_max[i+(1<<(j-1))][j -1]);27 dp_min[i][j] = min(dp_min[i][j-1],dp_min[i+(1<<(j-1))][j-1]);28 }29 }30 }31 }32 int main()33 {34 int n,q,m,k;35 scanf("%d%d",&n,&q); // 士兵的 总人数 .36 for(int i = 1; i <= n; i++)37 {38 scanf("%d",&dp_max[i][0]); // 39 dp_min[i][0]=dp_max[i][0]; // 最小和最大 都先默认了 40 }41 RMQ(n); // 一共 有 n 个 数字 42 while(q--)43 {44 scanf("%d%d",&m,&k);45 int s=(int)(log(k-m+1)/log(2));46 int max_val = max(dp_max[m][s],dp_max[k-(1<