ZeroJudge 解題筆記：e437. Segment Tree 練習2 + 區間修改

作者：王一哲
日期：2026年5月23日


ZeroJudge 題目連結：e437. Segment Tree 練習2 + 區間修改

解題想法

這題我只有寫 C++ 線段樹版本。

C++ 程式碼

線段樹，使用時間約為 80 ms，記憶體約為 45 MB，通過測試。

#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
typedef long long LL;
using namespace std;

struct QueryResult {  // 回傳查詢結果用的結構體
    LL sum_val;
    int max_val, min_val;
};

/* 本題重點，自訂線段樹類別，區間更新，記錄區間加總、最大值、最小值 */
class SegmentTree {
private:
    int n, mod;
    vector<int> data, imax, imin, lazy;
    vector<LL> isum;
    vector<bool> has_lazy;
    
    /* 內部遞迴函式 */
    void _push_up(int node) {
        isum[node] = (isum[2*node + 1] + isum[2*node + 2]) % mod;
        imax[node] = max(imax[2*node + 1], imax[2*node + 2]);
        imin[node] = min(imin[2*node + 1], imin[2*node + 2]);
    }

    void _build(int node, int start, int end) {
        // 遞迴出口
        if (start == end) {
            isum[node] = data[start] % mod;
            imax[node] = data[start];
            imin[node] = data[start];
            return;
        }
        // 遞迴，處理左、右半邊
        int mid = (end - start) / 2 + start;
        _build(2*node + 1, start, mid);
        _build(2*node + 2, mid + 1, end);
        _push_up(node);
    }
    
    void _push_down(int node, int start, int end) {
        if (has_lazy[node]) {
            int mid = (end - start) / 2 + start, val = lazy[node];
            // 處理左半邊
            int left_len = mid - start + 1;
            isum[2*node + 1] = (1LL * val * left_len) % mod;
            imax[2*node + 1] = val;
            imin[2*node + 1] = val;
            lazy[2*node + 1] = val;
            has_lazy[2*node + 1] = true;
            // 處理右邊
            int right_len = end - mid;
            isum[2*node + 2] = (1LL * val * right_len) % mod;
            imax[2*node + 2] = val;
            imin[2*node + 2] = val;
            lazy[2*node + 2] = val;
            has_lazy[2*node + 2] = true;
            has_lazy[node] = false;
        }
    }

    void _update(int node, int start, int end, int left, int right, int val) {
        // 遞迴出口，[start, end] 與 [left, right] 沒有交集
        if (end < left || start > right) return;
        // 遞迴出口，[left, right] 包含 [start, end]，更新 node 對應的值及標記
        if (left <= start && right >= end) {
            isum[node] = (1LL * val * (end - start + 1)) % mod;
            imax[node] = val;
            imin[node] = val;
            lazy[node] = val;
            has_lazy[node] = true;
            return;
        }
        // 先呼叫 _push_down，將標記往下傳，再用遞迴處理左、右兩半
        _push_down(node, start, end);
        int mid = (end - start) / 2 + start;
        _update(2*node + 1, start, mid, left, right, val);
        _update(2*node + 2, mid + 1, end, left, right, val);
        // 更新 node 對應的加總、最大值、最小值
        _push_up(node);
    }
    
    // 合併三個查詢功能
    QueryResult _query(int node, int start, int end, int left, int right) {
        // 遞迴出口，[start, end] 與 [left, right] 沒有交集
        if (end < left || start > right) {
            return {0, -2000000000, 2000000000};  // 0 給加總，max 給極小值，min 給極大值
        }
        // 遞迴出口，[left, right] 包含 [start, end]
        if (left <= start && right >= end) {
            return {isum[node], imax[node], imin[node]};
        }
        // 先 _push_down 再遞迴
        _push_down(node, start, end);
        int mid = (end - start) / 2 + start;
        QueryResult L = _query(2*node + 1, start, mid, left, right);
        QueryResult R = _query(2*node + 2, mid + 1, end, left, right);
        QueryResult res;
        res.sum_val = (L.sum_val + R.sum_val) % mod;
        res.max_val = max(L.max_val, R.max_val);
        res.min_val = min(L.min_val, R.min_val);
        return res;
    }

public:
    // 建構子，只計算 A[1] ~ A[N] 的最大值、最小值，不要對建 N 之後的值建立線段樹
    SegmentTree(const vector<int>& input_data, int target_n, int m) {
        data = input_data;
        n = target_n;
        mod = m;
        int tree_size = 4*n + 1;
        has_lazy.assign(tree_size, false);
        lazy.assign(tree_size, 0);
        isum.assign(tree_size, 0);
        imax.assign(tree_size, 0);
        imin.assign(tree_size, 0);
        if (n > 0) {
            _build(0, 1, n);
        }
    }

    /* 外部呼叫函式 */
    void update(int left, int right, int val) {
        _update(0, 1, n, left, right, val);
    }

    pair<int, int> query(int left, int right) {
        QueryResult res = _query(0, 1, n, left, right);
        return make_pair(res.sum_val, res.max_val - res.min_val);
    }
};

int main() {
    // 讀取測資
    int k, m, N, Q;
    scanf("%d %d", &k, &m);
    vector<int> A (k+1, 0);
    for(int i=1; i<=k; i++) {
        scanf("%d", &A[i]);
    }
    scanf("%d %d", &N, &Q);
    int limit = max(N, Q);
    A.resize(limit + 1);  // 調整 A 的長度
    // 第1個迴圈，填入 A[k+1] ~ A[limit]
    for(int i=k+1; i<=limit; i++) {
        A[i] = (A[i-2] * 97 + A[i-1] * 3) % m + 1;
    }
    // 第2個迴圈，計算 op, x, y 同時查詢或更新線段樹
    SegmentTree st(A, N, m);
    int j = limit;
    for(int i=1; i<=Q; i++) {
        bool op = A[i] & 1;
        int x = (A[i] + A[j]) % N + 1;
        int y = x + ((A[i] << 3) + (A[j] << 5) + m) % (N - x + 1);
        if (op) {  // 查詢
            auto it = st.query(x, y);
            printf("%d %d\n", it.first, it.second);
        } else {  // 更新
            int z = ((A[i] << 3) + (A[j] << 5)) % m + 1;
            st.update(x, y, z);
            //printf("%d %d %d %d\n", A[i], x, y, z);
        }
        j--;
    }
    return 0;
}