UVa11235 - Frequent values(線段樹)

題目大意

有一個非遞增的數列，雖然非遞增，但前一個數值必會小於等於這個數值，我們要查詢一個區間，想詢問這個區間中最常出現的數字次數是多少？

題目連結

重點觀念

• 線段樹的學習與應用
  如果需要學習演算法，請參考 大衞的筆記 - Segment Tree 線段樹
• 對於題目的仔細閱讀
• 我們線段樹應該要保存甚麼數值，才能解決此題

分析

只要遇到需要查詢區間的問題一律就要想到線段樹，線段樹的時間複雜度可以來到 \(O(n \ log \ n\)，能夠打遍百分之 90 的題目，但這邊有些小技巧要解決。

這題要在線段樹裡面存的就是題目所需要的出現次數，但可能會有一種疑問
Q: 1,2,3,3,3,3,4，如果我要找區間 \([4,5]\) 要怎麼辦呢，這裡 index 從 1 開始。

這個時候題目給了我們一個很大的提示，題目有說前一個數值必會小於等於這個數值，因此我們可以視為相同的數字只會出現在同個區段且不會再有其他區段重複。

區段： 1,1,1,1，這種連續數字在一塊地，定義為區塊

解決方法

我們透過舉例來說明這種解決方式，用題目測資來說明

index:  1   2  3  4  5  6  7   8   9  10
value: -1  -1  1  1  1  1  3  10  10  10
fre:    2   2  4  4  4  4  1   3   3   3

left:   1   1  2  2  2  2  7   8   8   8    
right:  2   2  6  6  6  6  6  10  10  10

如果我們要查詢的區間是 \([4,9]\)，此時如果按照存區塊最大值時答案會是 4，但這裡的區間不應該有 4，答案要是 3，遇到這種問題就很棘手XD。

但還是有辦法的，我們紀錄每個區塊的右邊界與左邊界，如果我們查詢的區間比起區塊還要小的時候就可以讓區塊的右邊界減去區間的左邊界，或區間的右邊界減去區塊的左邊界，這樣就可以避免掉區間查詢查到 4 的情況。

而且我們只要在一開始的去判斷這種區間切到區塊的問題，之後就不需要，我們可以將要查詢的範圍減掉左右兩區間所切到的區塊，依照範例就是變為 \([7,7]\)，\([4,6]) 則是被切掉的左區間、\([8,9]]\) 則是被切掉的右區間，那麼縮小範圍後的區間裡面必包含完整區塊。畢竟裡面的區塊我們都沒有動到，所以都是完整的，也不存在不完整的情況發生。
不完整的區間只有在一開始的查詢區間有可能出現。

這時我們再進行線段樹查詢找出最大出現數字次數，就能夠成功找到答案！

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

至於 大衞的筆記 - Segment Tree 線段樹 有做說明的部分，這邊就不在進行說明。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define Lson(x) x << 1
#define Rson(x) (x << 1) + 1
#define MAXN 100020
using namespace std;
int n, q, ta, tb;
struct tree{
    int l, r, v; //將 left right value 進行簡化為 l r v
    tree(){}
    tree(int _l, int _r, int _v): l(_l), r(_r), v(_v) {}
}node[4 * MAXN];
struct NUM{ //用來儲存區塊
    int l, r, f, v; 
    // l 區塊的左邊界
    // r 區塊的右邊界
    // f 區塊有多長
    // v 區塊的數值
}num[MAXN];


void build(int left, int right, int x = 1){
    node[x].l = left;
    node[x].r = right;

    if(left == right){
        node[x].v = num[left].f; //區塊有多長，題目詢問的重點
        return;
    }

    int mid = (left + right) / 2;
    build(left, mid, Lson(x));
    build(mid + 1, right, Rson(x));
    node[x].v = max(node[Lson(x)].v, node[Rson(x)].v);
}

int query(int left, int right, int x = 1){
    if(num[left].v == num[right].v) return right - left + 1;
    //題目所查詢的區間，剛好在同個區塊上，num[left].v == num[right].v 表示數值相同也就代表區塊相同
    // 因此只需要拿左區間邊界減去右區間邊界加一就可以得到答案

    int ans = 0;
    if(left > num[left].l){ //查詢的左區間邊界切到區塊，且此區間有數個區塊
        ans = num[left].r - left + 1; //計算切到的區間大小
        //方法是查詢被切到的區塊右邊界減去左區間邊界加一
        left = num[left].r + 1; //將左區間邊界移至被切區塊的右邊界加一，就不會切到區塊
    }
    if(right < num[right].r){ //查詢的右區間邊界切到區塊，且此區間有數個區塊
        ans = max(right - num[right].l + 1, ans); //計算切到的區間大小，並找出最大
        //方法是查詢的右邊界減掉區塊左邊界加一
        right = num[right].l - 1; //將右區間邊界移至被切區塊的左邊界減一，就不會切到區塊
        
    }
    //cout << "left right ans " << left << ' ' << right << ' ' << ans << '\n';
    if(left > right ) return ans; //如果左邊界大於右邊界，表示不需要再進行查詢直接回傳答案
    //由於上面的 +1、-1，因此有機會出現左邊界大於右邊界的情形。

    if(node[x].l >= left && node[x].r <= right ) return node[x].v; 
    int mid = (node[x].l + node[x].r) / 2;
    if(left <= mid) ans = max(ans, query(left, right, Lson(x)));
    if(mid < right) ans = max(ans, query(left, right, Rson(x)));
    return ans;
}

void debug_num(){ //debug 用 無意義
    for(int i = 1; i <= n; i++)
        cout << i << ' ' << num[i].l << ' ' << num[i].r << ' ' << num[i].v << ' ' << num[i].f << '\n';
    cout << '\n';
}

void debug_build(){ //debug 用 無意義
    for(int i = 1; i <= n; i++)
        cout << i << ' ' << node[i].l << ' ' << node[i].r << ' ' << node[i].v << '\n';
    cout << '\n';
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL

    int s = 1, e; //長度的 start ，長度的 end
    while(cin >> n >> q && n + q != 0){ //輸入資料，並且注意查詢可以為 0，因此 n + q 必須 != 0
        for(int i = 1; i <= n; i++){ //書資料
            cin >> ta;
            num[i].v = ta; //值設定 ta
            if(num[i].v != num[i-1].v){ //如果現在的值與前面的值不同，表示不同區塊
                for(int j = s; j < i; j++){ //將前面的區塊的左邊界、右邊界、長度進行設定。
                    num[j].l = s; //設定左邊界
                    num[j].r = i-1; //設定右邊界，i-1 是因為 i 已經是不同區塊 
                    num[j].f = i - s; //設定長度
                }
                s = i; //更新下個區塊的左邊界
            }
        }
        for(int j = s; j <= n; j++){ //最後一個區塊必須拉出來寫，因為後面沒有數值來進行分裂
            num[j].l = s;
            num[j].r = n;
            num[j].f = n - s + 1;
        }
        //debug_num();
        build(1, n);
        //debug_build();
        for(int i = 0; i < q; i++){ //輸出結果
            cin >> ta >> tb;
            cout << query(ta, tb) << '\n';
        }
    }



    return 0;
}

參考連結

UVa 11235 - Frequent values - naivered
algorithmist wiki

心得

這題複習了我很久沒有練習的線段樹，演算法太久沒有碰真的會忘記，今天在複習線段樹的時後一直卡卡的，腦袋還沒有喚醒記憶，透過今天的複習把記憶在喚醒！

這題的小巧思好棒，雖然我沒有在很短的時間想到怎麼解，但我透過學習 naivered 大大的想法，得知還有這種解法，希望我學習了這種解法能夠讓我在未來的路上用上！

題外話：人生一定要學習有意義的事情嗎？ 怎樣的事情算有意義。