POJ_3264

    这是一个RMQ问题，可以直接用线段树处理出区间的最大及最小值，在O(logN)的时间完成每次的查询操作。

#include
     
       #include
      
        #define MAXD 130000 #define INF 1000000000 int a[MAXD], b[MAXD], N, Q, M; void init() {
   int i, j, k;     memset(a, 0, sizeof(a));     memset(b, 0, sizeof(b)); for(M = 1; M < N + 2; M <<= 1); for(i = 0, j = M + 1; i < N; i ++, j ++)     {
           scanf("%d", &k);         a[j] = b[j] = k;     } for(i = M - 1; i; i --)     {
           a[i] = a[2 * i + 1]; if(a[i] == 0 || (a[2 * i] != 0 && a[2 * i] < a[i]))             a[i] = a[2 * i];         b[i] = b[2 * i + 1]; if(b[2 * i] > b[i])             b[i] = b[2 * i];     } } void solve() {
   int i, s, t, min, max; for(i = 0; i < Q; i ++)     {
           scanf("%d%d", &s, &t);         min = INF;         max = 0;         s = s - 1 + M;         t = t + 1 + M; for(;s ^ t ^ 1; s >>= 1, t >>= 1)         {
   if(~s & 1)             {
   if(a[s ^ 1] && a[s ^ 1] < min)                     min = a[s ^ 1]; if(b[s ^ 1] > max)                     max = b[s ^ 1];             } if(t & 1)             {
   if(a[t ^ 1] && a[t ^ 1] < min)                     min = a[t ^ 1]; if(b[t ^ 1] > max)                     max = b[t ^ 1];             }         }         printf("%d\n", max - min);     } } int main() {
   while(scanf("%d%d", &N, &Q) == 2)     {
           init();         solve();     } return 0; }