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序列有良好的部分单调性。