ヒホ16週目
978 ワード
RMQ-SITアルゴリズム
タイトル:n個の数を入力して、l,rを与えて、この区間の最小値を調べます.典型的なRMQアルゴリズムです.
コードは以下の通りです
タイトル:n個の数を入力して、l,rを与えて、この区間の最小値を調べます.典型的なRMQアルゴリズムです.
コードは以下の通りです
#include
#define maxn 1000001
using namespace std;
int a[maxn], d[maxn][20];
void init( int n){
for ( int i = 0; i < n; i++)
d[i][0] = a[i];
for ( int j = 1; ( 1 << j) <= n; j++){
for ( int i = 0; i + ( 1 << j) - 1 < n; i++)
d[i][j] = min( d[i][j - 1], d[i + ( 1 << ( j - 1))][j - 1]);
}
}
int RMQ( int l, int r){
int k = 0;
while ( 1 << ( k + 1) <= r - l + 1) k++;
return min( d[l][k], d[r - ( 1 << k) + 1][k]);
}
int main()
{
int n, q, l, r;
scanf( "%d", &n);
for ( int i = 0; i < n; i++){
scanf( "%d", &a[i]);
}
init( n);
scanf( "%d", &q);
while ( q--){
scanf( "%d%d", &l, &r);
printf( "%d
", RMQ( l - 1, r - 1));
}
return 0;
}