LightOJ - 1082 - Array Queries

1. #include <bits/stdc++.h>
2. #define R 100003
3. using namespace std;
4.  
5. int numbers[R], tree[R*3], I, J;
6.  
7. void build(int u, int v, int node){
8.     if(u >= v){
9.         if(u == v)tree[node] = numbers[u];
10.         return;
11.     }
12.     int mid = (u+v)/2, child1 = node*2, child2 = node*2+1;
13.     build(u, mid, child1);
14.     build(mid+1, v, child2);
15.     tree[node] = min(tree[child1], tree[child2]);
16. }
17.  
18. int query(int u, int v, int node){
19.     if(u > J || v < I)return INT_MAX;
20.     if(u >= I && v <= J)return tree[node];
21.     if(u > v)return INT_MAX;
22.     int mid = (u+v)/2, child1 = node*2, child2 = node*2+1;
23.     int x = query(u, mid, child1);
24.     int y = query(mid+1, v, child2);
25.     return min(x, y);
26. }
27.  
28. int main(){
29.     int cs = 0, n, q, t;
30.     scanf("%d", &t);
31.     while(t--){
32.         scanf("%d %d", &n, &q);
33.         for(int i = 1; i <= n; i++)scanf("%d", &numbers[i]);
34.         build(1, n, 1);
35.         printf("Case %d:\n", ++cs);
36.         for(int i = 1; i <= q; i++){
37.             scanf("%d %d", &I, &J);
38.             printf("%d\n", query(1, n, 1));
39.         }
40.     }
41.     return 0;
42. }