九度OJ 1544 数字序列区间最小值 - c++编程基础

题目描述：

给定一个数字序列，查询任意给定区间内数字的最小值。

输入：

输入包含多组测试用例，每组测试用例的开头为一个整数n(1<=n<=100000)，代表数字序列的长度。
接下去一行给出n个数字，代表数字序列。数字在int范围内。
下一行为一个整数t(1<=t<=10000)，代表查询的次数。
最后t行，每行给出一个查询，由两个整数表示l、r(1<=l<=r<=n)。

输出：

对于每个查询，输出区间[l,r]内的最小值。

样例输入：

样例输出：

1
1
3

//Trivial algorithms for RMQ
#include 
  
   
#include 
   
     #include 
    
      void Preprocess (int arr[], int n, int loc[]){ int i, j, k; int step; int min; step = (int)sqrt((double)n); i = j = k = 0; while (1){ min = k*step; for (j=k*step+1; j
     
       arr[j]) min = j; } loc[k] = min; ++k; if (j >= n) break; } } int main(void){ int n; int arr[100001]; int loc[1000]; int t; int i; int left; int right; int min; int step; int index; while (scanf (%d, &n) != EOF){ step = (int)sqrt((double)n); for (i=0; i
      
        
        






        
       //Sparse Table (ST) algorithm
#include 
        
         
#include 
         
           #include 
          
            #define MAX 100000 #define LOGMAX 20 void Preprocess (int M[MAX][LOGMAX], int arr[MAX], int n){ int i, j; for (i = 0; i < n; ++i) M[i][0] = i; for (j = 1; 1 << j <= n; ++j){ for (i = 0; i + (1 << j) - 1 < n; ++i){ if (arr[M[i][j - 1]] < arr[M[i + (1 << (j - 1))][j - 1]]) M[i][j] = M[i][j - 1]; else M[i][j] = M[i + (1 << (j - 1))][j - 1]; } } } int main(void){ int n; int arr[MAX]; int M[MAX][LOGMAX]; int test; int left; int right; int i; int min; int k; while (scanf (%d, &n) != EOF){ for (i = 0; i < n; ++i){ scanf (%d, &arr[i]); } Preprocess (M, arr, n); scanf (%d, &test); while (test-- != 0){ scanf (%d%d, &left, &right); --left; --right; k = 0; while ((1 << (k + 1)) < (right - left + 1)) ++k; if (arr[M[left][k]] <= arr[M[right - (1 << k) + 1][k]]) min = arr[M[left][k]]; else min = arr[M[right - (1 << k) + 1][k]]; printf (%d , min); } } return 0; } /************************************************************** Problem: 1544 User: 简简单单Plus Language: C Result: Accepted Time:270 ms Memory:9040 kb ****************************************************************/
          
         
         
       
 参考资料：http://community.topcoder.com/tc module=Static&d1=tutorials&d2=lowestCommonAncestor 
         
       http://dongxicheng.org/structure/lca-rmq/ 
       http://dongxicheng.org/structure/segment-tree/