RMQ(Range Minimum/Maximum Query)問題：
?
預處理:
預處理使用DP的思想，f(i, j)表示[i, i+2^j - 1]區(qū)間中的最小值，我們可以開辟一個數(shù)組專門來保存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的區(qū)間: [m, m+2^k-1], [n-2^k+1, n];
而我們之前已經(jīng)求出了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))
感想：對于一個數(shù)組里的固定長度的區(qū)間，可以只開一個n*1維數(shù)組，算f(i,j)的時候可以將f(i,j-1)覆蓋，因為用到的只是上一列的情況。
?
題目：
poj 3368 Frequent values
http://poj.org/problem?id=3368
?
題意 ： 給定 一個 遞增的數(shù)組 a?? 給出 q 次詢問 求出 l? 到 r? 最多的???? 數(shù)字相同的個數(shù)
?
如 ：10 3 -1 -1 1 1 1 1 3 10 10 10
輸入 1 10
輸出? 4
? 1 到10 出現(xiàn)最多的是 1 出現(xiàn)了 4 次
?
題解： 將 連續(xù)相同的點 縮成一個節(jié)點 ，這個節(jié)點包括三個部分? 初始位置 ，結(jié)束位置 ，個數(shù)
? 那么詢問時 包括三種情況
? 1:l 和 r同屬于? 一個節(jié)點?? 那么 ans = r - l + 1
? ?
? 2： 屬于相鄰的連個節(jié)點? ans =? max ( p[hash[l]].t - l +1,r - p[hash[r]].s + 1);
? 3: 屬于? l 和 r之間有好幾個節(jié)點?? 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
?
題意 ： 給定 一段數(shù)?? 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);
}
}
}
?
?
?
?
?
更多文章、技術交流、商務合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
