d539: 區間 MAX

 1#include <bits/stdc++.h>
 2using namespace std;
 3
 4int arr[500001], N;
 5int nodes[2000001]; // 每個節點都儲存自己區間的答案，並且節點號碼從 1 開始，才能遵循 LeftChild: 2 倍、RightChild: 2 倍 + 1 原則
 6inline int left(int p) { return p << 1; }
 7inline int right(int p) { return left(p) + 1; }
 8int build(int p, int l, int r) { // 求出區間 [l-r] 的答案並儲存進號碼 p 的節點
 9    // assert(l <= r); // 從中間剖分的過程中，左索引值不可能超過右索引值
10    if (l == r) return nodes[p] = arr[l]; // 區間為單點元素時只得自行計算出答案
11    int m = (l + r) >> 1; // 取中點
12    auto a1 = build(left(p), l, m); // 求出區間 [l-m] 的答案並儲存進號碼 2p 的節點
13    auto a2 = build(right(p), m+1, r); // 求出區間 [(m+1)-r] 的答案並儲存進號碼 2p + 1 的節點
14    return nodes[p] = max(a1, a2); // 合併左右子樹的兩個答案以求出自己的答案，並存進節點中
15}
16int L, R; // 用於 recursive 和 query，表示欲查詢區間為 [L-R]
17int recursive(int p, int l, int r) { // assert(l <= r); // 給定過程中已經有答案的節點區間 [l-r]，最後會回傳此區間和欲查詢區間 [L-R] 交集之後的答案，注意這三個數字本應與 build 過程中所設定的一致
18    if (r < L || R < l) return -INT_MAX; // 如果節點區間與欲查詢區間沒有重疊，則希望此答案為單位元素 (做運算之後不影響其他區間的答案)
19    if (L <= l && r <= R) return nodes[p]; // 如果節點區間已經被完整包覆在欲查詢區間之內，則直接貢獻答案 (停止繼續遞迴)
20    // 如果節點區間和欲查詢區間僅部分重疊，則把自己這個節點區間再切成兩半，分別繼續做 recursive
21    int m = (l + r) >> 1; // 取中點，注意到下面的 left(p), l, m 和 right(p), m+1, r 的 pattern 會與 build 的過程完全相同
22    return max(recursive(left(p), l, m), recursive(right(p), m+1, r));
23}
24int query(int l, int r) {
25    L = l; R = r; // assert(L <= R); // 欲查詢區間 [L-R] 在計算過程中不會改變
26    return recursive(1, 1, N); // 給定大區間 [1-N] 內所有子區間的已知資料，如何求出恰為 [L-R] 區間的答案？
27}
28
29int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
30    cin >> N;
31    for (int i=1; i<=N; i++) cin >> arr[i];
32    build(1, 1, N);
33    int M; cin >> M;
34    while (M--) {
35        int a, b; cin >> a >> b;
36        if (a > b) swap(a, b);
37        cout << query(a, b) << endl;
38    }
39    return 0;
40}