LightOJ 1082 Solution

Array Queries Solution

#include<bits/stdc++.h>

#define mx 100009

#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

int st[24][mx], a[mx];

void sparse_table(int n)

{

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

        st[0][i] = i;

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

    {

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

        {

            int j = k-1;

            int x = st[j][i];

            int y = st[j][i+(1<<j)];

            st[k][i] = a[x]<=a[y] ? x:y;

        }

    }

}

int rmq(int i, int j)

{

    int k = log2(j-i+1);

    int x = st[k][i];

    int y = st[k][j-(1<<k)+1];

    return a[x]<=a[y] ? x:y;

}

int main()

{

    fast

    int t, k = 1;

    cin >> t;

    while(t--)

    {

        int n, q, x, y;

        cin >> n >> q;

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

            cin >> a[i];

        sparse_table(n);

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

        while(q--)

        {

            cin >> x >> y;

            x--, y--;

            cout << a[rmq(x, y)] << "\n";

        }

    }

    return 0;

}