Wednesday, March 11, 2020

SPOJ - RMQSQ - Range Minimum Query

Problem Link: https://www.spoj.com/problems/RMQSQ/

IDEA: Use sparse table to do this problem. Simple sparse table implementation.


CODE:

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define sf scanf(a)

int st[100008][27];

void precompute(int a[],int n, int k)
{
    for(int i=0;i<n;i++)
    {
        st[i][0]=a[i];
    }

    for(int j=1;j<=k;j++)
    {
        for(int i=0;i+(1<<j)<=n;i++)
        {
            st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
        }
    }
}


int main()
{
    int n;
    cin>>n;
    int a[n+5];
    for(int i=0;i<n;i++)
        cin>>a[i];
    int log[n+5];
    log[1]=0;
    for(int i=2;i<=n;i++)
        log[i]=log[i/2]+1;
    int k=log[n]+1;
    precompute(a,n,k);
    int q;
    cin>>q;
    for(int i=0;i<q;i++)
    {
        int l,r;
        ll sum=0;
        cin>>l>>r;
        int x=log[r-l+1];
        sum=min(st[l][x],st[r-(1<<(x))+1][x]);
        cout<<sum<<endl;
    }
    return 0;
}


No comments:

Post a Comment