題目：
RMQ problem
Time limit = 5 second(s)
Memory limit = 32000 Kb
You are given large array of real numbers:
a[0], a[1], ..., a[N-1]
Range Minimal Query problem:
Problem RMQ(i,j) = "find minimum of a[i], a[i+1], ..., a[j-1]".
Your program should solve given set of RMQ problems.
Input. Input data has the following format:
N
a[0] a[1] ... a[N-1]
M
i1 j1
i2 j2
...
iM jM
Here N ≤ 250000, M ≤ 500000, 0 ≤ ik < N, 0 < jk ≤ N, ik < jk.
Output. Your program should output M numbers b1, b2, ..., bM delimited by space, where
bk = MIN (a[ik], a[ik + 1], ..., a[jk — 1]).
Input#1
10
1 2 3 4 5 6 7 8 9 10
16
0 1
0 2
0 3
0 4
3 4
3 5
3 6
3 7
3 8
3 9
3 10
0 10
9 10
8 10
7 10
5 6
Output#1
1.000000
1.000000
1.000000
1.000000
4.000000
4.000000
4.000000
4.000000
4.000000
4.000000
4.000000
1.000000
10.000000
9.000000
8.000000
6.000000
Input#2
10
3.86934 7.28362 2.15556 14.75963 0.33240 17.12550 -0.71121 13.90834 -1.13470 5.99831
11
6 10
0 1
5 10
1 9
0 6
0 10
2 5
3 10
5 9
0 8
2 10
Output#2
-1.134700
3.869340
-1.134700
-1.134700
0.332400
-1.134700
0.332400
-1.134700
-1.134700
-0.711210
-1.134700
代碼：
[cpp]
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
using namespace std;
#define N 250010
int n,m;
int x,y;
float A[N];
int M[N][19];
void process()
{
for(int i=0;i<n;i++)
{
M[i][0] = i;
}
for(int j=1;(1<<j)<=n;j++)
{
for(int i=0;i+(1<<j)-1<n;i++)
{
if(A[M[i][j-1]]<A[M[i+(1<<(j-1))][j-1]])
{
M[i][j] = M[i][j-1];
}
else
{
M[i][j] = M[i+(1<<(j-1))][j-1];
}
}
}
}
float query(int x,int y)
{
int k;
k = (int)(log(y-x+1)/log(2));
return A[M[x][k]]<A[M[y-(1<<k)+1][k]] ? A[M[x][k]] : A[M[y-(1<<k)+1][k]];
}
int main()
{
/*#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif*/
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf(" %f",&A[i]);
}
process();
scanf(" %d",&m);
for(int i=0;i<m;i++)
{
scanf(" %d%d",&x,&y);
printf("%f\n",query(x,y-1));
}
return 0;
}
