Messy

范围最值查询 RMQ

范围最值查询(RMQ)

RMQ的一般形式表述为:对于长度为n的数列A,查询q(l, r),返回A[l…r]之间的最大值(最小值等)。

POJ 3368

Portal: http://poj.org/problem?id=3368

题意:

有一个单调不减的序列a[n], 问子序列a[l…r]中,出现次数最多的数的出现次数(好像有点拗口,还是看例子吧)。
比如:序列为 -1 -1 1 1 1 1 3 10 10 10,a[5…10]中,出现次数最多的数是10,它的出现次数是3,所以要输出3。

解题思路:

算是比较直白的RMQ模板题。对于区间a[l...r],如果a[l]这个数在此前的序列中没有出现过,那么问题就可以简单地转化为RMQ的基本形式,即查询l到r的区间内出现次数的最大值。这里只要把a[l]在此前序列中已经出现的情况考虑一下即可。
对于上述序列,我们先定义长度为n的数列freq,表示这个数已经出现的次数,即1 2 1 2 3 4 1 1 2 3。此序列用于前面所述的纯RMQ过程。
如果a[l]在此前已经出现过,那么就把序列分成a[l...t]a[t+1...r]两部分,其中a[l…r]中的数都是a[l]。最后答案取max(t-l+1, RMQ(t+1, r))

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <ctype.h>
#include <cmath>
#define MAXN 100010
using namespace std;
int n, q;
int a[MAXN];
int freq[MAXN];
int goback[MAXN];
int st[MAXN][20];
void initRMQ(){
for (int i = 1; i <= n; ++i) {
st[i][0] = freq[i];
}
int k = log((double)(n + 1)) / log(2.0);
for (int j = 1; j <= k; ++j) {
for (int i = 1; i + (1<<j) - 1 <= n; i++) {
st[i][j] = max( st[i][j - 1],
st[i + (1 << (j-1))][j - 1] );
}
}
}
int RMQ(int l, int r){
if(l > r)
return 0;
int k = log((double)(r - l + 1)) / log(2.0);
return max(st[l][k], st[r - (1 << k) + 1][k]);
}
int main(){
while (cin >> n && n) {
cin >> q;
a[0] = -1;
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
freq[1] = 1;
for (int i = 2; i <= n; ++i) {
if (a[i] == a[i-1]) {
freq[i] = freq[i-1]+1;
}
else freq[i] = 1;
}
int t;
for (int i = n; i >= 1; i -= t) {
t = freq[i];
for (int j = i - t + 1; j <= i; j++) {
goback[j] = t;
}
}
//a: -1 -1 1 1 1 1 3 10 10 10
//freq: 1 2 1 2 3 4 1 1 2 3
//goback: 2 2 4 4 4 4 1 3 3 3
initRMQ();
int l, r, tmp;
while (q--) {
scanf("%d %d", &l, &r);
tmp = min(goback[l] - freq[l] , r - l );
cout << max(tmp + 1, RMQ(tmp + l + 1, r)) << endl;
}
}
}

此方法可以AC,但是还有一些优化空间。因为freq序列有良好的部分单调性。