日期：2026年5月24日
ZeroJudge 題目連結：e457. 也是 Segment Tree 練習
解題想法
單點修改，查詢區間連乘的正負號，不需要真的存數字，如果數字大於 0 存 1，等於 0 存 0，小於 0 存 -1。
Python 程式碼
使用時間約為 1.1 s，記憶體約為 33.9 MB，通過測試。
class SegmentTree:
def __init__(self, data):
self.n = len(data)
self.data = [0]
for d in data:
if d > 0:
self.data.append(1)
elif d == 0:
self.data.append(0)
else:
self.data.append(-1)
self.tree = [0]*(4 * self.n)
if self.n > 0:
self._build(0, 1, self.n)
# --- 內部遞迴函式 ---
def _build(self, node, start, end):
if start == end:
if self.data[start] > 0:
self.tree[node] = 1
elif self.data[start] == 0:
self.tree[node] = 0
else:
self.tree[node] = -1
return
mid = (end - start) // 2 + start
self._build(2*node + 1, start, mid)
self._build(2*node + 2, mid + 1, end)
self.tree[node] = self.tree[2*node + 1] * self.tree[2*node + 2]
def _update(self, node, start, end, target, val):
if start == end:
if val > 0:
self.tree[node] = 1
self.data[target] = 1
elif val == 0:
self.tree[node] = 0
self.data[target] = 0
else:
self.tree[node] = -1
self.data[target] = -1
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)
self.tree[node] = self.tree[2*node + 1] * self.tree[2*node + 2]
def _query(self, node, start, end, left, right):
if end < left or start > right:
return 1
if left <= start and right >= end:
return self.tree[node]
mid = (end - start) // 2 + start
lval = self._query(2*node + 1, start, mid, left, right)
rval = self._query(2*node + 2, mid + 1, end, left, right)
return lval * rval
# --- 外部呼叫函式 ---
def update(self, target, val):
self._update(0, 1, self.n, target, val)
def query(self, left, right):
return self._query(0, 1, self.n, left, right)
def solve():
import sys
result = []
data = sys.stdin.read().split()
ptr = 0
while ptr < len(data):
n = int(data[ptr])
k = int(data[ptr+1])
ptr += 2
nums = list(map(int, data[ptr:ptr+n]))
ptr += n
st = SegmentTree(nums)
for i in range(k):
op = data[ptr]
x = int(data[ptr+1])
y = int(data[ptr+2])
ptr += 3
if op == "C":
st.update(x, y)
else:
z = st.query(x, y)
if z == 1:
result.append("+")
elif z == 0:
result.append("0")
else:
result.append("-")
result.append("\n")
sys.stdout.write("".join(result))
if __name__ == "__main__":
solve()
