LightOJ 1082 Solution

Array Queries : Solution

#include<bits/stdc++.h>

#define mx 100002

using namespace std;

int a[mx];

int tree[mx*3];

void initialize(int node, int s, int e)

{

    if(s == e)

    {

        tree[node] = a[s];

        return;

    }

    int left = node*2;

    int right = node*2 + 1;

    int mid = (s+e)/2;

    initialize(left, s, mid);

    initialize(right, mid+1, e);

    tree[node] = min(tree[left], tree[right]);

}

int query(int node, int s, int e, int i, int j)

{

    if(i > e || j < s)

        return 10e6;

    if(s >= i && e <= j)

        return tree[node];

    int left = node*2;

    int right = node*2+1;

    int mid = (s+e)/2;

    int r1 = query(left, s, mid, i, j);

    int r2 = query(right, mid+1, e, i, j);

    return min(r1, r2);

}

int main()

{

    int t, k = 1;

    cin >> t;

    while(t--)

    {

        int n, q;

        cin >> n >> q;

        for(int i=1; i<=n; i++)

            cin >> a[i];

        initialize(1, 1, n);

        cout << "Case " << k++ << ":\n";

        while(q--)

        {

            int i, j;

            cin >> i >> j;

            cout << query(1, 1, n, i, j) << "\n";

        }

    }

    return 0;

}