日期：2026年5月22日
ZeroJudge 題目連結：e409. Segment Tree 練習
解題想法
這類型不斷地更新某個位置的值，不斷地查詢區域加總的題目，基本上都是用線段樹或二元索引樹處理。用 C++ 解題兩種寫法都能過關。用 Python 解題，遞迴版的線段樹與二元索引樹都太慢，後來是用非遞迴版的線段樹才過關。
Python 程式碼
遞迴版線段樹，從測資 #4 開始超時。
import sys
sys.setrecursionlimit(10000)
# --- 本題重點，自訂線段樹類別，單點更新，記錄區間最大值、最小值 ---
class SegmentTree:
def __init__(self, data, n):
self.data = data
self.n = n
self.imax = [0] * (4*self.n + 1)
self.imin = [0] * (4*self.n + 1)
if self.n > 0:
self._build(0, 1, self.n) # 題目的 A 是 1-index
# --- 內部遞迴函式 ---
def _build(self, node, start, end):
# 遞迴出口
if start == end:
self.imax[node] = self.data[start]
self.imin[node] = self.data[start]
return
# 遞迴，處理左、右半邊
mid = (end - start) // 2 + start
self._build(2*node + 1, start, mid)
self._build(2*node + 2, mid + 1, end)
# 更新 node 對應的最大值、最小值
self.imax[node] = max(self.imax[2*node + 1], self.imax[2*node + 2])
self.imin[node] = min(self.imin[2*node + 1], self.imin[2*node + 2])
def _update(self, node, start, end, target, val):
# 遞迴出口
if start == end:
self.imax[node] = val
self.imin[node] = val
self.data[target] = val
return
# 遞迴，處理左、右半邊
mid = (end - start) // 2 + start
if target <= mid: # 在左側
self._update(2*node + 1, start, mid, target, val)
else: # 在右側
self._update(2*node + 2, mid + 1, end, target, val)
# 更新 node 對應的最大值、最小值
self.imax[node] = max(self.imax[2*node + 1], self.imax[2*node + 2])
self.imin[node] = min(self.imin[2*node + 1], self.imin[2*node + 2])
def _query(self, node, start, end, left, right):
# 遞迴出口，[start, end] 與 [left, right] 沒有交集
if end < left or start > right:
return (-2000000000, 2000000000)
# 遞迴出口，[left, right] 包含 [start, end]
if left <= start and right >= end:
return (self.imax[node], self.imin[node])
# 遞迴，處理左、右半邊
mid = (end - start) // 2 + start
L = self._query(2*node + 1, start, mid, left, right)
R = self._query(2*node + 2, mid + 1, end, left, right)
return (max(L[0], R[0]), min(L[1], R[1]))
# --- 外部呼叫函式 ---
def update(self, target, val):
self._update(0, 1, self.n, target, val)
def query(self, left, right):
res = self._query(0, 1, self.n, left, right)
return res[0] - res[1]
# --- 主要的解題過程 ---
def solve():
import sys
result = []
data = sys.stdin.read().split()
ptr = 0
while ptr < len(data):
MaxN, MaxQ = 1000005, 100005
k = int(data[ptr])
m = int(data[ptr+1])
ptr += 2
A = [0]*MaxN
for i in range(1, k+1):
A[i] = int(data[ptr])
ptr += 1
N = int(data[ptr])
Q = int(data[ptr+1])
ptr += 2
C = [False]*MaxQ
X = [0]*MaxQ
Y = [0]*MaxQ
# 題目中給定的産生資料函式
def gen_dat():
# 第一個迴圈
limit = max(Q, N)
i = k+1
while i <= limit:
A[i] = (A[i-2]*97 + A[i-1]*3) % m + 1
i += 1
# 第二個迴圈
i = 1
j = limit
while i <= Q:
C[i] = A[i] & 1
X[i] = (A[i] + A[j]) % N + 1
if C[i]: Y[i] = X[i]+ ( (A[i] << 3) + (A[j] << 5) + m ) % (N - X[i] + 1)
else: Y[i] = ((A[i] << 3) + (A[j] << 5)) % m + 1
i += 1
j -= 1
# 呼叫 gen_dat() 産生 A 的完整內容
gen_dat()
#print(A[:26]) # 印出前 26 項檢查內容
# 讀取 operations 並輸出答案
st = SegmentTree(A, N)
for i in range(1, Q+1):
op, x, y = C[i], X[i], Y[i]
if op == 0:
st.update(x, y)
elif op == 1:
result.append(f"{st.query(x, y):d}\n")
sys.stdout.write("".join(result))
if __name__ == "__main__":
solve()
二元索引樹，只能通過 48％ 的測資。
class BIT_RMQ:
def __init__(self, A):
self.n = len(A) - 1 # 這題的 A 是 1-index
self.A = A[:] # 複製一份
self.imax = [-200000000] * (self.n + 1) # 存區間最大值
self.imin = [200000000] * (self.n + 1) # 存區間最大值
for i in range(1, self.n + 1):
self._recalculate(i)
def _lowbit(self, x):
return x & (-x)
def _recalculate(self, i):
# 重新計算 tree[i] 及 tree[i-2], tree[i-4], tree[i-8], ...
max_val = self.A[i]
min_val = self.A[i]
j = 1
while j < self._lowbit(i):
if self.imax[i-j] > max_val: max_val = self.imax[i-j]
if self.imin[i-j] < min_val: min_val = self.imin[i-j]
j <<= 1
self.imax[i] = max_val
self.imin[i] = min_val
def update(self, i, val):
self.A[i] = val
while i <= self.n:
self._recalculate(i)
i += self._lowbit(i)
def query(self, left, right):
max_val = min_val = self.A[right]
while right >= left:
if right - self._lowbit(right) >= left - 1:
if self.imax[right] > max_val: max_val = self.imax[right]
if self.imin[right] < min_val: min_val = self.imin[right]
right -= self._lowbit(right)
else:
if self.A[right] > max_val: max_val = self.A[right]
if self.A[right] < min_val: min_val = self.A[right]
right -= 1
return max_val - min_val
def solve():
import sys
data = sys.stdin.read().split()
if not data: return
result = []
ptr = 0
while ptr < len(data):
k = int(data[ptr])
m = int(data[ptr+1])
ptr += 2
# 提前抓取 N, Q 決定 limit
N = int(data[ptr + k])
Q = int(data[ptr + k + 1])
limit = max(Q, N)
A = [0] * (limit + 1)
for i in range(1, k+1):
A[i] = int(data[ptr])
ptr += 1
# 略過剛剛抓取的 N 和 Q
ptr += 2
# 第一個迴圈：產生 A 的完整內容
for i in range(k+1, limit+1):
A[i] = (A[i-2] * 97 + A[i-1] * 3) % m + 1
# 初始化 BIT_RMQ
bit = BIT_RMQ(A)
# 第二個迴圈：生成測資同時更新、查詢
j = limit
for i in range(1, Q + 1):
op = A[i] & 1
x = (A[i] + A[j]) % N + 1
if op == 1: # 查詢指令
y = x + ((A[i] << 3) + (A[j] << 5) + m) % (N - x + 1)
ans = bit.query(x, y)
result.append(f"{ans:d}\n")
else: # 更新指令
y = ((A[i] << 3) + (A[j] << 5)) % m + 1
bit.update(x, y)
j -= 1
sys.stdout.write("".join(result))
if __name__ == "__main__":
solve()
C++ 程式碼
線段樹，使用時間約為 35 ms，記憶體約為 40.9 MB，通過測試。
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
/* 本題重點，自訂線段樹類別，單點更新，記錄區間最大值、最小值 */
class SegmentTree {
private:
int n;
vector<int> data, imax, imin;
/* 內部遞迴函式 */
void _build(int node, int start, int end) {
// 遞迴出口
if (start == end) {
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);
// 更新 node 對應的最大值、最小值
imax[node] = max(imax[2*node + 1], imax[2*node + 2]);
imin[node] = min(imin[2*node + 1], imin[2*node + 2]);
}
void _update(int node, int start, int end, int target, int val) {
// 遞迴出口
if (start == end) {
imax[node] = val;
imin[node] = val;
data[target] = val;
return;
}
// 遞迴，處理左、右半邊
int mid = (end - start) / 2 + start;
if (target <= mid) { // 在左側
_update(2*node + 1, start, mid, target, val);
} else { // 在右側
_update(2*node + 2, mid + 1, end, target, val);
}
// 更新 node 對應的最大值、最小值
imax[node] = max(imax[2*node + 1], imax[2*node + 2]);
imin[node] = min(imin[2*node + 1], imin[2*node + 2]);
}
pair<int, int> _query(int node, int start, int end, int left, int right) {
// 遞迴出口，[start, end] 與 [left, right] 沒有交集
if (end < left || start > right) {
return make_pair(-2000000000, 2000000000);
}
// 遞迴出口，[left, right] 包含 [start, end]
if (left <= start && right >= end) {
return make_pair(imax[node], imin[node]);
}
// 遞迴，處理左、右半邊
int mid = (end - start) / 2 + start;
auto L = _query(2*node + 1, start, mid, left, right);
auto R = _query(2*node + 2, mid + 1, end, left, right);
return make_pair(max(L.first, R.first), min(L.second, R.second));
}
public:
// 建構子，只計算 A[1] ~ A[N] 的最大值、最小值，不要對建 N 之後的值建立線段樹
SegmentTree(const vector<int>& input_data, int target_n) {
data = input_data;
n = target_n;
imax.assign(4*n + 1, 0);
imin.assign(4*n + 1, 0);
if (n > 0) {
_build(0, 1, n);
}
}
/* 外部呼叫函式 */
void update(int target, int val) {
_update(0, 1, n, target, val);
}
int query(int left, int right) {
auto res = _query(0, 1, n, left, right);
return res.first - res.second;
}
};
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);
int j = limit;
for(int i=1; i<=Q; i++) {
bool op = A[i] & 1;
int x = (A[i] + A[j]) % N + 1;
if (op) { // 查詢
int y = x + ((A[i] << 3) + (A[j] << 5) + m) % (N - x + 1);
printf("%d\n", st.query(x, y));
} else { // 更新
int y = ((A[i] << 3) + (A[j] << 5)) % m + 1;
st.update(x, y);
}
j--;
}
return 0;
}
二元索引樹，使用時間約為 55 ms，記憶體約為 18 MB，通過測試。
#include <cstdio>
#include <vector>
using namespace std;
class BIT_RMQ {
private:
int n;
vector<int> arr, imax, imin;
public:
BIT_RMQ(const vector<int>& A) {
n = (int)A.size() - 1;
arr.resize(n + 1);
imax.assign(n + 1, -200000000);
imin.resize(n + 1, 200000000);
for(int i=1; i<=n; i++) {
arr[i] = A[i];
}
for(int i=1; i<=n; i++) {
_recalculate(i);
}
}
int _lowbit(int x) {
return x & (-x);
}
void _recalculate(int i) {
int max_val = arr[i], min_val = arr[i];
int j = 1;
while(j < _lowbit(i)) {
if (imax[i-j] > max_val) max_val = imax[i-j];
if (imin[i-j] < min_val) min_val = imin[i-j];
j <<= 1;
}
imax[i] = max_val;
imin[i] = min_val;
}
void update(int i, int val) {
arr[i] = val;
while(i <= n) {
_recalculate(i);
i += _lowbit(i);
}
}
int query(int left, int right) {
int max_val = arr[right], min_val = arr[right];
while(right >= left) {
if (right - _lowbit(right) >= left - 1) {
if (imax[right] > max_val) max_val = imax[right];
if (imin[right] < min_val) min_val = imin[right];
right -= _lowbit(right);
} else {
if (arr[right] > max_val) max_val = arr[right];
if (arr[right] < min_val) min_val = arr[right];
right--;
}
}
return max_val - 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 同時查詢或更新線段樹
BIT_RMQ bit(A);
int j = limit;
for(int i=1; i<=Q; i++) {
bool op = A[i] & 1;
int x = (A[i] + A[j]) % N + 1;
if (op) { // 查詢
int y = x + ((A[i] << 3) + (A[j] << 5) + m) % (N - x + 1);
printf("%d\n", bit.query(x, y));
} else { // 更新
int y = ((A[i] << 3) + (A[j] << 5)) % m + 1;
bit.update(x, y);
}
j--;
}
return 0;
}
沒有留言:
張貼留言