RMQ（log2储存方法）

RMQ

难度级别：B；运行时间限制：1000ms；运行空间限制：256000KB；代码长度限制：2000000B

试题描述

长度为n的数列A，以及q个询问，每次询问一段区间的最小值。

输入

第一行，一个整数n
第二行，n个数，表示A数组，用空格隔开。
第三行，一个正整数q
第4到第q+3行每行两个正整数L、R（L<=R），表示一段区间，用一个空格隔开。

输出

针对每个询问，输出结果。每个结果占一行。

输入示例

5
3 2 4 3 5
3
1 3
2 5
3 4

输出示例

2
2
3

其他说明

数据规模：n, q, Ai<=100000

 1 #include<iostream>
 2 
 3 #include<cmath>
 4 
 5 using namespace std;
 6 
 7 int f[100010][20];
 8 
 9 void rmq(int num)
10 
11 {
12 
13     for(int j=1;j<20;j++)
14 
15         for(int i=1;i<=num;i++)
16 
17             if(i+(1<<j)-1<=num)
18 
19                 f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
20 
21 }
22 
23 int main()
24 
25 {
26 
27     int i,j,n,t,m;
28 
29     scanf("%d",&n);
30 
31     for(i=1;i<=n;i++)
32 
33     {
34 
35         scanf("%d",&f[i][0]);
36 
37     }
38 
39     rmq(n);
40 
41     int s,p,maxl,minl;
42 
43     cin>>m;
44 
45     while(m--)
46 
47     {
48 
49         scanf("%d%d",&s,&p);
50 
51         int k=(int)((log(p-s+1))/log(2.0));
52 
53         minl=min(f[s][k],f[p-(1<<k)+1][k]);
54 
55         printf("%d\n",minl);
56 
57     }
58 
59 }

View Code

RMQ（log2储存方法）

推荐阅读