一、题意

输入n、q（n、q<=100000），然后输入一个长度为n的递增序列A（有重复元素）。
之后是q次询问，每次询问输入两个数l、r，你需要输出在区间 A[l...r] 中出现次数最多的元素的出现次数。

二、解析

为了不超时，每次询问我们需要在O(1)~O(lgn)时间内作出回答。这就让我们想到有一个在O(1)时间内得到区间最值的算法：RMQ算法。

在本题中，就是要在一个cnt数组中得到某个区间中的cnt最大值。

因此我们很自然地需要对原序列进行统计，得到一个“把相同值聚类”后的新数组，为了方便起见，还需要维护每一个值在原数组的左边界和右边界，因此这里我用一个结构体来保存，即代码中的segment类。

由于题目询问时给出的是原数组的下标，因此我们还需要一个从原数组下面映射到新数组下标的映射数组seg_idx[maxn]。

之后求出现次数的最值就变得简单了，即最大值将会是以下3个值之一：

  • l到它所在的segment的右边界的长度
  • r到它所在的segment的左边界的长度
  • RMQ_cnt(segment[seg_idx[l] + 1], segment[seg_idx[r]]) ，即segmemt[l所在segment的下标+1, r所在segment的下标)

三、代码

#include <iostream>
#include <cmath>
using namespace std;
const int maxn = 100000 + 5, log2_maxn = (int)log2(maxn) + 5;
struct segment {
    int val, cnt, l, r;  // 左闭右闭
    segment() {}
    segment(int val, int cnt, int l, int r) : val(val), cnt(cnt), l(l), r(r) {}
} seg[maxn];
int n, q, a[maxn], seg_id[maxn], dp[maxn][log2_maxn];

void RMQ_init(int m) {
    for(int i = 0; i < m; i ++) dp[i][0] = seg[i].cnt;  // 左闭右开
    for(int j = 1; (1 << j) < m; j ++) {
        for(int i = 0; i + (1 << j) - 1 < m; i ++)
            dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j-1))][j - 1]);
    }
}

int RMQ_max(int l, int r) {  // 左闭右开
    if(l >= r) return 0;
    int k = log2(r - l);
    return max(dp[l][k], dp[r - (1 << k)][k]);
}

int main() {
    while(cin >> n && n) {
        cin >> q;
        for(int i = 0; i < n; i ++) cin >> a[i];

        int idx = 0;
        seg[0] = segment(a[0], 1, 0, 0), seg_id[0] = 0;
        for(int r = 1; r < n; r ++) {
            if(a[r] == seg[idx].val) seg[idx].cnt ++, seg[idx].r = r;
            else idx ++, seg[idx] = segment(a[r], 1, r, r);
            seg_id[r] = idx;
        }
        RMQ_init(idx + 1);

        while(q --) {
            int l, r, ans;
            cin >> l >> r;
            l --, r --;
            if(seg_id[l] == seg_id[r]) ans = r - l + 1;
            else ans = max(max(seg[seg_id[l]].r - l + 1, r - seg[seg_id[r]].l + 1),
                          RMQ_max(seg_id[l] + 1, seg_id[r]));
            cout << ans << endl;
        }
    }
}

四、归纳

  • RMQ算法：实现在O(1)时间内得到数组中某个下标区间内的最值，注意RMQ中的区间一般表示为左闭右开，即[l, r)。下面是以最大值为例的模板： 
#include <cmath>

const int maxn = 100000 + 5, log2_maxn = (int)log2(maxn) + 5;
int a[maxn], dp[maxn][log2_maxn];

// 通过动态规划得到dp[i][j]数组，表示原数组a[maxn]中区间a[i, i + 2^j)中的最大值
void RMQ_init(int n) {
    for(int i = 0; i < n; i ++) dp[i][0] = a[i];  // 只有一个数的区间
    for(int j = 1; (1 << j) < n; j ++) {  // 大区间由小区间计算而成，因此从小到大枚举j
        for(int i = 0; i + (1 << j) - 1 < n; i ++)  // 循环边界条件：i + 2^j - 1为最后一个下标
            dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j-1))][j - 1]);
    }
}

int RMQ_max(int l, int r) {  // 左闭右开
    if(l >= r) return 0;
    int k = log2(r - l);
    return max(dp[l][k], dp[r - (1 << k)][k]);  // 通过取两个区间的最值来处理log造成的误差问题
}
  • 当题目与区间相关时，最好统一好使用左闭右开区间来表示，或者统一左闭右闭，否则容易出错