Problem link: 1082 - Array Queries
N.B: This is a segment tree problem. If you do not know about segment tree, spend some time to learn it and please try at least 1 hour to solve it yourself before seeing other's solution. Happy coding!
- #include <bits/stdc++.h>
- using namespace std;
- #define MAX 200005
- int a[MAX];
- int tree[MAX * 3];
- void init(int node, int b, int e)
- {
- if (b == e) {
- tree[node] = a[b];
- return;
- }
- int left = node * 2;
- int right = node * 2 + 1;
- int mid = (b + e) / 2;
- init(left, b, mid);
- init(right, mid + 1, e);
- tree[node] = min(tree[left], tree[right]);
- }
- int query(int node, int b, int e, int i, int j)
- {
- int x, y;
- if (i > e || j < b)
- return INT_MAX;
- if (b >= i && e <= j)
- return tree[node];
- int Left = node * 2;
- int Right = node * 2 + 1;
- int mid = (b + e) / 2;
- x = query(Left, b, mid, i, j);
- y = query(Right, mid + 1, e, i, j);
- return min(x, y);
- }
- int main() {
- int t;
- cin >> t;
- for (int tc = 1; tc <= t; tc++)
- {
- int n, q;
- scanf("%d%d", &n, &q);
- for (int b = 1; b <= n; b++)
- scanf("%d", &a[b]);
- init(1, 1, n);
- printf("Case %d:\n", tc);
- for (int b = 1; b <= q; b++)
- {
- int i, j;
- scanf("%d%d", &i, &j);
- printf("%d\n", query(1, 1, n, i, j));
- }
- }
- return 0;
- }