LightOJ 1082 - Array Queries

// Straight forward RMQ (ST)

//Next Codeforces Round #354 (Div. 2)
#include<bits/stdc++.h>

//#include<cstdio>
//#include<iostream>
//#include<algorithm>
//#include<vector>
//#include<cstring>
//#include<cmath>
//#include<map>

using namespace std;

#define fast ios_base::sync_with_stdio(false)
#define bfast cin.tie(0)
#define outs(x) cout << x << " "
#define outn(x) cout << x << "\n"
#define sf scanf
#define pf printf
#define nl puts("")
#define psb push_back
//#define i64 long long
#define high 100005

typedef long long LL;
typedef vector<int>vii;
typedef vector<LL>vll;

int ar[high] , tree[high * 4]={-1};

void build(int node , int b , int e)
{
    if(b == e)
    {
        tree[node] = b;
        //return;
    }

    else
    {
        int left = node * 2;
        int right = (node * 2) + 1;
        int mid = (b + e) / 2;

        build(left, b , mid);
        build(right , mid + 1 , e);

        if(ar[tree[left]] <= ar[tree[right]])
        {
            tree[node] = tree[left];
        }

        else
        {
            tree[node] = tree[right];
        }
    }
}

int query(int node , int b , int e , int i , int j)
{
    if(i > e or j < b) return -1;

    if(b >= i and e <= j)
    {
        return tree[node];
    }

    int left = node * 2;
    int right = (node * 2) + 1;
    int mid = (b + e) / 2;

    int pek = query(left, b , mid, i, j);
    int pdui = query(right, mid+1, e , i , j);

    if(pek == -1) return pdui;
    if(pdui == -1) return pek;
    if(ar[pek] <= ar[pdui]) return pek;
   return pdui;
}

int main()
{
    int t , tc=0 , n , q , i , j , indx;
    sf("%d", &t);
    while(t--)
    {
        sf("%d %d", &n , &q);

        for(i=0; i<n; i++)
        {
            sf("%d", &ar[i]);
        }

        build(1 , 0, n-1);

        pf("Case %d:\n", ++tc);

        while(q--)
        {
            sf("%d %d", &i , &j);

            indx = query(1 , 0, n-1, i-1 , j-1);

            pf("%d\n" , ar[indx]);
        }
    }

    return 0;
}