RMQ(Range Minimum/Maximum Query)问题：
预处理:
预处理使用DP的思想，f(i, j)表示[i, i+2^j - 1]区间中的最小值，我们可以开辟一个数组专门来保存f(i, j)的值。
例如，f(0, 0)表示[0,0]之间的最小值,就是num[0], f(0, 2)表示[0, 3]之间的最小值, f(2, 4)表示[2, 17]之间的最小值
注意, 因为f(i, j)可以由f(i, j - 1)和f(i+2^(j-1), j-1)导出, 而递推的初值(所有的f(i, 0) = i)都是已知的
所以我们可以采用自底向上的算法递推地给出所有符合条件的f(i, j)的值。
1
for
(
int
i=
1
;i<=n;i++
)
2
f[i,
0
]:=
a[i];
3
4
for
(
int
j=
1
;j<=log(n)/log(
2
);j++
)
5
{
6
for
(
int
i=
1
;i<=n+
1
-
1
<<j;j++
)
7
f[i,j]=max(f[i,j-
1
],f[i+
1
<<(j-
1
),j-
1
]);
8
};
查询:
假设要查询从m到n这一段的最小值, 那么我们先求出一个最大的k, 使得k满足2^k <= (n - m + 1).
于是我们就可以把[m, n]分成两个(部分重叠的)长度为2^k的区间: [m, m+2^k-1], [n-2^k+1, n];
而我们之前已经求出了f(m, k)为[m, m+2^k-1]的最小值, f(n-2^k+1, k)为[n-2^k+1, n]的最小值
1
long
query(
long
l,
long
r)
2
{
3
long
x=log(r-l+
1
)/log(
2
);
4
return
(max(f[l,x],f[r+
1
-
1
<<
x,x]));
5
}
我们只要返回其中更小的那个, 就是我们想要的答案, 这个算法的时间复杂度是O(1)的.
例如, rmq(0, 11) = min(f(0, 3), f(4, 3))
感想：对于一个数组里的固定长度的区间，可以只开一个n*1维数组，算f(i,j)的时候可以将f(i,j-1)覆盖，因为用到的只是上一列的情况。
题目：
poj 3368 Frequent values
http://poj.org/problem?id=3368
题意 ： 给定 一个 递增的数组 a 给出 q 次询问 求出 l 到 r 最多的 数字相同的个数
如 ：10 3 -1 -1 1 1 1 1 3 10 10 10
输入 1 10
输出 4
1 到10 出现最多的是 1 出现了 4 次
题解： 将 连续相同的点 缩成一个节点 ，这个节点包括三个部分 初始位置 ，结束位置 ，个数
那么询问时 包括三种情况
1:l 和 r同属于 一个节点 那么 ans = r - l + 1
2： 属于相邻的连个节点 ans = max ( p[hash[l]].t - l +1,r - p[hash[r]].s + 1);
3: 属于 l 和 r之间有好几个节点 hash[l]+1 到 hash[r] - 1 的最大值 和 情况 2 进
View Code
1
#include<cstdio>
2
#include<cmath>
3
#include<cstring>
4
#include<iostream>
5
#include<algorithm>
6
#include<
set
>
7
#include<map>
8
#include<queue>
9
#include<vector>
10
#include<
string
>
11
#define
Min(a,b) a<b?a:b
12
#define
Max(a,b) a>b?a:b
13
#define
CL(a,num) memset(a,num,sizeof(num));
14
#define
maxn 100010
15
#define
inf 9999999
16
17
#define
mod 9973
18
#define
ll long long
19
using
namespace
std;
20
int
hash[maxn],a[maxn];
21
int
dp[maxn][
30
],id;
22
23
struct
node
24
{
25
int
s;
26
int
t;
27
int
w;
28
29
}p[maxn];
30
void
rmq_init()
31
{
32
int
i , j;
33
34
for
( i =
0
; i <= id;++i)dp[i][
0
] =
p[i].w;
35
int
k = log(
double
(id+
1.0
))/log(
2.0
);
//
36
37
for
( i =
1
;i <= k; ++
i)
38
{
39
int
s = (
1
<< i-
1
) -
1
;
40
for
(j =
1
;j + (
1
<< i)-
1
<= id ;++
j)
41
{
42
dp[j][i] = max(dp[j][i -
1
],dp[j + s ][i -
1
]);
43
}
44
}
45
}
46
int
get
(
int
l,
int
r)
47
{
48
int
k = log(
double
(r - l +
1.0
))/log(
2.0
);
//
求的是 求出最大的k,满足2^k<=R-L+1
49
int
s =
1
<<
k;
50
return
max(dp[l][k],dp[r - s +
1
][k]);
51
}
52
int
main()
53
{
54
int
n,m,i,l,r;
55
while
(scanf(
"
%d
"
,&
n),n)
56
{
57
scanf(
"
%d
"
,&
m);
58
for
( i =
1
;i <=n; ++i)scanf(
"
%d
"
,&
a[i]);
59
60
memset(p,
0
,
sizeof
(p));
61
id =
1
;
62
p[
1
].s =
1
;
63
64
for
( i =
1
; i <= n ;++
i)
65
{
66
hash[i] =
id ;
67
p[id].w++
;
68
if
( a[i] != a[i+
1
] || i ==
n)
69
{
70
p[id].t =
i;
71
if
(i == n)
break
;
72
id++
;
73
p[id].s = i +
1
;
74
75
}
76
77
}
78
rmq_init();
79
80
while
( m--
)
81
{
82
scanf(
"
%d%d
"
,&l,&
r);
83
if
(hash[l] == hash[r])printf(
"
%d\n
"
,r - l +
1
);
84
else
85
{
86
int
num1 = p[hash[l]].t - l +
1
;
87
int
num2 = r - p[hash[r]].s +
1
;
88
int
num3 =
0
;
89
if
(hash[r] - hash[l] >
1
)
90
num3 =
get
(hash[l]+
1
,hash[r]-
1
);
91
int
ans =
max(max(num1,num2),num3);
92
printf(
"
%d\n
"
,ans);
93
}
94
}
95
}
96
}
poj 3264 Balanced Lineup
http://poj.org/problem?id=3264
题意 ： 给定 一段数 q此次询问 求出 l 到 r 的 最大值 和最小值的
View Code
#include<cstdio>
#include
<cstring>
#include
<iostream>
#include
<algorithm>
#include
<
set
>
#include
<map>
#include
<queue>
#include
<vector>
#include
<
string
>
#define
Min(a,b) a<b?a:b
#define
Max(a,b) a>b?a:b
#define
CL(a,num) memset(a,num,sizeof(num));
#define
maxn 60000
#define
inf 9999999
#define
mod 9973
#define
ll long long
using
namespace
std;
int
dp1[maxn][
30
],dp2[maxn][
30
],a[maxn];
int
n,m;
void
RMQ_init()
{
int
temp =
0
,i,j,s;
while
(
1
<< temp < n)temp++
;
for
(i =
0
;i <= n; ++i)dp1[i][
0
] = dp2[i][
0
] =
a[i];
for
(i =
1
; i <= temp ; ++
i)
{
s
=
1
<< (i-
1
);
for
(j =
0
; j + s <= n;++
j)
{
dp1[j][i]
= max(dp1[j][i-
1
],dp1[j + s][i-
1
]);
dp2[j][i]
= min (dp2[j][i-
1
],dp2[j + s][i -
1
]);
}
}
}
int
get
(
int
l,
int
r)
{
int
k = r - l +
1
;
int
tmp =
0
;
while
(
1
<< tmp < k ) tmp++
;
tmp
--
;
int
s =
1
<<
tmp;
int
mx = max(dp1[l][tmp],dp1[r +
1
-
s][tmp]);
int
mi = min(dp2[l][tmp],dp2[r +
1
-
s ][tmp]);
return
mx -
mi ;
}
int
main()
{
int
i, l,r;
while
(scanf(
"
%d%d
"
,&n,&m)!=
EOF)
{
for
(i =
1
;i <= n; ++
i)
scanf(
"
%d
"
,&
a[i]);
RMQ_init();
while
(m--
)
{
scanf(
"
%d%d
"
,&l,&
r);
int
ans =
get
(l ,r);
printf(
"
%d\n
"
,ans);
}
}
}
