POJ.3264 Balanced Lineup

1.Problem
http://poj.org/problem?id=3264

2.Idea
Two segment trees for Min and Max range queries.

3.Source

 const int MAX_N = 1 << 17;  
 const int I_MAX = 1 << 25;  
 const int I_MIN = -1;  
 int n, q, nn, datMin[2 * MAX_N - 1], datMax[2 * MAX_N - 1];  
 void update(int k, int a)  
 {  
      k += nn - 1;  
      datMin[k] = a;  
      datMax[k] = a;  
      while (k > 0) {  
           k = (k - 1) / 2;  
           datMin[k] = min(datMin[k * 2 + 1], datMin[k * 2 + 2]);  
           datMax[k] = max(datMax[k * 2 + 1], datMax[k * 2 + 2]);  
      }  
 }  
 int queryMin(int a, int b, int k, int l, int r)  
 {  
      if (r <= a || b <= l) return I_MAX;  
      if (a <= l && r <= b) return datMin[k];  
      else {  
           int v1 = queryMin(a, b, k * 2 + 1, l, (l + r) / 2);  
           int v2 = queryMin(a, b, k * 2 + 2, (l + r) / 2, r);  
           return min(v1, v2);  
      }  
 }  
 int queryMax(int a, int b, int k, int l, int r)  
 {  
      if (r <= a || b <= l) { return I_MIN; }  
      if (a <= l && r <= b) { return datMax[k]; }  
      else {  
           int v1 = queryMax(a, b, k * 2 + 1, l, (l + r) / 2);  
           int v2 = queryMax(a, b, k * 2 + 2, (l + r) / 2, r);  
           return max(v1, v2);   
      }  
 }  
 int main()  
 {  
      scanf("%d%d", &n, &q);  
      nn = 2;  
      while (n > nn) nn *= 2;  
      for (int i = 0; i <= nn; i++) {  
           datMin[i] = I_MAX;  
           datMax[i] = I_MIN;  
      }  
      for (int i = 1; i <= n; i++) {  
           int tmp;  
           scanf("%d", &tmp);  
           update(i, tmp);  
      }  
      for (int i = 0; i < q; i++) {  
           int l, r;  
           scanf("%d%d", &l, &r);  
           printf("%d\n", queryMax(l, r + 1, 0, 0, nn) - queryMin(l, r + 1, 0, 0, nn));  
      }  
      return 0;  
 }