Lightoj 1082 - Array Queries

http://lightoj.com/volume_showproblem.php?problem=1082

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define mx 100001
4. int arr[mx];
5. int tree[mx * 3];
6. void init(int node, int b, int e)
7. {
8.     if (b == e) {
9.         tree[node] = arr[b];
10.         return;
11.     }
12.     int Left = node * 2;
13.     int Right = node * 2 + 1;
14.     int mid = (b + e) / 2;
15.     init(Left, b, mid);
16.     init(Right, mid + 1, e);
17.     tree[node] = min(tree[Left], tree[Right]);
18. }
19. int query(int node, int b, int e, int i, int j)
20. {
21.     if (i > e || j < b)
22.         return INT_MAX; //বাইরে চলে গিয়েছে
23.     if (b >= i && e <= j)
24.         return tree[node]; //রিলেভেন্ট সেগমেন্ট
25.     int Left = node * 2; //আরো ভাঙতে হবে
26.     int Right = node * 2 + 1;
27.     int mid = (b + e) / 2;
28.     int p1 = query(Left, b, mid, i, j);
29.     int p2 = query(Right, mid + 1, e, i, j);
30.     return min(p1,p2); //বাম এবং ডান পাশের যোগফল
31. }
32.  
33. int main()
34. {
35.     int ts;
36.     scanf("%d", &ts);
37.     for(int p = 1; p <=ts; p++){
38.     printf("Case %d:\n", p);
39.     int n, q;
40.     scanf("%d%d", &n, &q);
41.     for(int i = 1; i <= n; i++) scanf("%d", &arr[i]);  
42.     init(1, 1, n);
43.     for(int i = 0;i <q; i++){
44.         int a, b;
45.         scanf("%d%d", &a, &b);
46.         printf("%d\n",query(1, 1, n, a, b));
47.     }
48.     }
49.     return 0;
50. }