BOJ - 14245 - XOR
Updated:
import sys, math
def init(arr, tree, node, start, end):
if start == end:
tree[node] = arr[start]
return tree[node]
mid = (start + end) // 2
tree[node] = init(arr, tree, node * 2, start, mid) ^ \
init(arr, tree, node * 2 + 1, mid + 1, end)
return tree[node]
def updateLazyTree(tree, lazy, node, start, end):
if lazy[node] != 0:
tree[node] ^= lazy[node] * ((end - start + 1) % 2)
if start != end:
lazy[node * 2] ^= lazy[node]
lazy[node * 2 + 1] ^= lazy[node]
lazy[node] = 0
def updateValue(tree, lazyTree, node, start, end, left, right, value):
updateLazyTree(tree, lazyTree, node, start, end)
if (right < start or end < left): return tree[node]
elif (left <= start and end <= right):
tree[node] ^= value * ((end - start + 1) % 2)
if start != end:
lazyTree[node * 2] ^= value
lazyTree[node * 2 + 1] ^= value
return tree[node]
mid = (start + end) // 2
tree[node] = updateValue(tree, lazyTree, node * 2, start, mid, left, right, value) ^ \
updateValue(tree, lazyTree, node * 2 + 1, mid + 1, end, left, right, value)
return tree[node]
def xorValue(tree, lazy, node, start, end, left, right):
updateLazyTree(tree, lazy, node, start, end)
if (right < start or end < left): return 0
elif (left <= start and end <= right): return tree[node]
mid = (start + end) // 2
return xorValue(tree, lazy, node * 2, start, mid, left, right) ^ \
xorValue(tree, lazy, node * 2 + 1, mid + 1, end, left, right)
def solution():
N = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
height = int(math.ceil(math.log2(N)))
treeSize = 1 << (height + 1)
segmentTree = [0] * treeSize
lazySegmentTree = [0] * treeSize
init(arr, segmentTree, 1, 0, N-1)
M = int(sys.stdin.readline())
for i in range(M):
command = list(map(int, sys.stdin.readline().split()))
if command[0] == 1:
updateValue(segmentTree, lazySegmentTree, 1, 0, N-1, command[1], command[2], command[3])
else:
print(xorValue(segmentTree, lazySegmentTree, 1, 0, N-1, command[1], command[1]))
solution()
https://www.acmicpc.net/problem/14245
Leave a comment