UVa 11235 Frequent Values：游程編碼與區間最大值查詢解題詳解

UVa 11235 Frequent Values 題目分析

UVa 11235 Frequent Values 是一道經典的區間查詢問題。給定一個非遞減序列，需多次查詢某區間內出現次數最多的數值的頻率。由於序列有序，相同數值會連續出現，這啟發我們使用游程編碼壓縮數據，再配合稀疏表實現 O(1) 區間最大值查詢。

核心思路：游程編碼 + RMQ

1. 游程編碼壓縮數據

將原序列壓縮為若干「段」，每段記錄：

• value[i]：第 i 段的數值
• count[i]：該數值連續出現的次數
• num[pos]：原序列位置 pos 所屬的段編號
• left[seg], right[seg]：段的左右端點在原序列中的位置

例如序列 5 5 5 7 7 3 3 3 2 2 2 2 1 1 1 1 1 1 1 壓縮為：

(5,3) (7,2) (3,3) (2,4) (1,7)

2. 區間查詢拆解

查詢區間 [L, R] 時，答案為以下三部分的最大值：

1. 左邊界段：從 L 到該段結束的元素個數 right[num[L]] - L + 1
2. 右邊界段：從該段開始到 R 的元素個數 R - left[num[R]] + 1
3. 中間完整段：若 num[L] + 1 <= num[R] - 1，查詢 count 陣列在該範圍的最大值（RMQ）

特殊情況：若 L、R 在同一段，答案直接為 R - L + 1。

3. 稀疏表實現 RMQ

預處理 d[i][j] 表示從 i 開始長度 2^j 區間的最大值，查詢時取兩個覆蓋區間的最大值，時間複雜度 O(1)。

完整代碼實現

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 100005;
const int LOG = 17;  // 2^17 > 100000

int n, q;
int a[MAXN];
int value[MAXN], cnt[MAXN];
int num[MAXN], Lpos[MAXN], Rpos[MAXN];
int st[MAXN][LOG];
int lg2[MAXN];

void buildRMQ(int segCnt) {
    for (int i = 1; i <= segCnt; ++i) st[i][0] = cnt[i];
    for (int j = 1; (1 << j) <= segCnt; ++j) {
        for (int i = 1; i + (1 << j) - 1 <= segCnt; ++i) {
            st[i][j] = max(st[i][j-1], st[i + (1 << (j-1))][j-1]);
        }
    }
    lg2[1] = 0;
    for (int i = 2; i <= segCnt; ++i) lg2[i] = lg2[i>>1] + 1;
}

int queryRMQ(int l, int r) {
    if (l > r) return 0;
    int k = lg2[r - l + 1];
    return max(st[l][k], st[r - (1 << k) + 1][k]);
}

int main() {
    while (scanf("%d", &n) == 1 && n) {
        scanf("%d", &q);
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);

        // 游程編碼
        int segCnt = 0;
        value[++segCnt] = a[1];
        cnt[segCnt] = 1;
        num[1] = segCnt;
        Lpos[segCnt] = 1;
        for (int i = 2; i <= n; ++i) {
            if (a[i] == a[i-1]) {
                cnt[segCnt]++;
                num[i] = segCnt;
            } else {
                Rpos[segCnt] = i - 1;
                value[++segCnt] = a[i];
                cnt[segCnt] = 1;
                num[i] = segCnt;
                Lpos[segCnt] = i;
            }
        }
        Rpos[segCnt] = n;

        buildRMQ(segCnt);

        while (q--) {
            int L, R;
            scanf("%d%d", &L, &R);
            if (num[L] == num[R]) {
                printf("%d\n", R - L + 1);
            } else {
                int ans = max(Rpos[num[L]] - L + 1, R - Lpos[num[R]] + 1);
                ans = max(ans, queryRMQ(num[L] + 1, num[R] - 1));
                printf("%d\n", ans);
            }
        }
    }
    return 0;
}

複雜度分析

• 預處理：O(n log n) 建立稀疏表
• 單次查詢：O(1)
• 空間複雜度：O(n log n)

此解法充分利用了序列非遞減的特性，將問題轉化為區間最大值查詢，是處理此類「頻率統計」問題的經典範例。