日期：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()
C++ 程式碼
使用時間約為 56 ms，記憶體約為 5 MB，通過測試。
#include <cstdio>
#include <vector>
using namespace std;
class SegmentTree {
private:
int n;
vector<int> data, tree;
/* 內部遞迴函式 */
void _build(int node, int start, int end) {
if (start == end) {
if (data[start] > 0) { // 只存正1、負-1、零0
tree[node] = 1;
} else if (data[start] < 0) {
tree[node] = -1;
} else {
tree[node] = 0;
}
return;
}
int mid = (end - start) / 2 + start;
_build(2*node + 1, start, mid);
_build(2*node + 2, mid + 1, end);
tree[node] = tree[2*node + 1] * tree[2*node + 2];
}
void _update(int node, int start, int end, int target, int val) {
if (start == end) {
if (val > 0) {
tree[node] = 1;
data[target] = 1;
} else if (val == 0) {
tree[node] = 0;
data[target] = 0;
} else {
tree[node] = -1;
data[target] = -1;
}
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);
}
tree[node] = tree[2*node + 1] * tree[2*node + 2];
}
int _query(int node, int start, int end, int left, int right) {
if (end < left || start > right) return 1;
if (left <= start && right >= end) return tree[node];
int mid = (end - start) / 2 + start;
int lval = _query(2*node + 1, start, mid, left, right);
int rval = _query(2*node + 2, mid + 1, end, left, right);
return lval * rval;
}
public:
// 建構子
SegmentTree(const vector<int>& input_data) {
n = (int)input_data.size();
data.resize(n+1);
for(int i=0; i<n; i++) {
if (input_data[i] > 0) data[i+1] = 1;
else if (input_data[i] == 0) data[i+1] = 0;
else data[i+1] = -1;
}
tree.assign(4*n, 0); // 只存正1、負-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) {
return _query(0, 1, n, left, right);
}
};
int main() {
int n, k;
while(scanf("%d %d", &n, &k) != EOF) {
vector<int> input_data(n);
for(int i=0; i<n; i++) {
scanf("%d", &input_data[i]);
}
SegmentTree st(input_data);
for(int i=0; i<k; i++) {
char op;
int x, y;
scanf(" %c %d %d", &op, &x, &y);
if (op == 'C') {
st.update(x, y);
} else {
int z = st.query(x, y);
if (z == 1) printf("+");
else if (z == 0) printf("0");
else printf("-");
}
}
printf("\n");
}
return 0;
}
沒有留言:
張貼留言