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