結果
| 問題 | No.3671 Reusable Lazy Segment Tree |
| コンテスト | |
| ユーザー |
 harurun
|
| 提出日時 | 2026-08-05 07:49:31 |
| 言語 | PyPy3 (7.3.23 + ACL) |
| 結果 |
TLE
不安定
|
| 実行時間 | - |
| コード長 | 18,211 bytes |
| 記録 | |
| コンパイル時間 | 252 ms |
| コンパイル使用メモリ | 95,944 KB |
| 実行使用メモリ | 328,704 KB |
| 最終ジャッジ日時 | 2026-09-04 22:03:30 |
| 合計ジャッジ時間 | 14,661 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 9 TLE * 1 -- * 9 |
ソースコード
#!/usr/bin/env python3
from array import array
import sys
BITS = 30
VALUE_MASK = (1 << BITS) - 1
LOW15_MASK = (1 << 15) - 1
_BIT_POS_LO = tuple(tuple(b for b in range(15) if mask & (1 << b))
for mask in range(1 << 15))
_BIT_POS_HI = tuple(tuple(b + 15 for b in bits) for bits in _BIT_POS_LO)
def parse_input():
data = sys.stdin.buffer.read()
if not data or data[-1] > 32:
data += b"\0"
i = 0
while data[i] <= 32:
i += 1
n = 0
while data[i] > 32:
n = n * 10 + data[i] - 48
i += 1
while data[i] <= 32:
i += 1
m = 0
while data[i] > 32:
m = m * 10 + data[i] - 48
i += 1
def read_array(length, leading_zero=False, data=data):
nonlocal i
out = array("I", [0]) * (length + leading_zero)
j = 1 if leading_zero else 0
end = j + length
while j < end:
while data[i] <= 32:
i += 1
value = 0
while data[i] > 32:
value = value * 10 + data[i] - 48
i += 1
out[j] = value
j += 1
return out
initial = read_array(n)
left_data = read_array(m, True)
right_data = read_array(m, True)
mask_data = read_array(m, True)
sum_left_data = read_array(m, True)
sum_right_data = read_array(m, True)
while data[i] <= 32:
i += 1
problem_count = 0
while data[i] > 32:
problem_count = problem_count * 10 + data[i] - 48
i += 1
starts = array("I", [0]) * problem_count
counts = array("I", [0]) * problem_count
k = 0
while k < problem_count:
while data[i] <= 32:
i += 1
value = 0
while data[i] > 32:
value = value * 10 + data[i] - 48
i += 1
starts[k] = value
while data[i] <= 32:
i += 1
value = 0
while data[i] > 32:
value = value * 10 + data[i] - 48
i += 1
counts[k] = value
k += 1
return (n, m, initial, left_data, right_data, mask_data,
sum_left_data, sum_right_data, problem_count, starts, counts)
def build_tree(values):
n = len(values)
size = 1
while size < n:
size <<= 1
nodes = size << 1
total = array("Q", [0]) * nodes
counts = array("I", [0]) * (nodes * BITS)
any_bits = array("I", [0]) * nodes
all_bits = array("I", [0]) * nodes
lazy_and = array("I", [VALUE_MASK]) * nodes
lazy_or = array("I", [0]) * nodes
saved = bytearray(nodes)
base = size
bit_pos_lo = _BIT_POS_LO
bit_pos_hi = _BIT_POS_HI
low15 = LOW15_MASK
for i, value in enumerate(values):
p = base + i
total[p] = value
any_bits[p] = value
all_bits[p] = value
count_base = p * 30
for b in bit_pos_lo[value & low15]:
counts[count_base + b] = 1
for b in bit_pos_hi[value >> 15]:
counts[count_base + b] = 1
for p in range(size - 1, 0, -1):
left = p << 1
right = left | 1
total[p] = total[left] + total[right]
any_bits[p] = any_bits[left] | any_bits[right]
all_bits[p] = all_bits[left] & all_bits[right]
count_base = p * 30
left_base = left * 30
right_base = right * 30
for b in range(30):
counts[count_base + b] = counts[left_base + b] + counts[right_base + b]
history = []
history_append = history.append
def save_full(p,
total=total, counts=counts,
any_bits=any_bits, all_bits=all_bits,
lazy_and=lazy_and, lazy_or=lazy_or,
saved=saved, history_append=history_append):
saved[p] = 1
count_base = p * 30
history_append((p, total[p], any_bits[p], all_bits[p],
lazy_and[p], lazy_or[p],
counts[count_base:count_base + 30]))
def push_nonidentity(p, half, parent_and, parent_or,
total=total, counts=counts,
any_bits=any_bits, all_bits=all_bits,
lazy_and=lazy_and, lazy_or=lazy_or,
saved=saved,
bit_pos_lo=bit_pos_lo, bit_pos_hi=bit_pos_hi,
low15=low15, save_full=save_full):
child = p << 1
count_base = child * 30
child_and = lazy_and[child]
child_or = lazy_or[child]
new_and = (child_and & parent_and) | parent_or
new_or = (child_or & parent_and) | parent_or
old_any = any_bits[child]
old_all = all_bits[child]
clear_bits = old_any & (VALUE_MASK ^ parent_and)
set_bits = parent_or & (VALUE_MASK ^ old_all)
changed = clear_bits | set_bits
if changed or new_and != child_and or new_or != child_or:
if not saved[child]:
save_full(child)
value = total[child]
for b in bit_pos_lo[clear_bits & low15]:
index = count_base + b
value -= counts[index] << b
counts[index] = 0
for b in bit_pos_hi[clear_bits >> 15]:
index = count_base + b
value -= counts[index] << b
counts[index] = 0
for b in bit_pos_lo[set_bits & low15]:
index = count_base + b
old_count = counts[index]
value += (half - old_count) << b
counts[index] = half
for b in bit_pos_hi[set_bits >> 15]:
index = count_base + b
old_count = counts[index]
value += (half - old_count) << b
counts[index] = half
total[child] = value
any_bits[child] = (old_any & parent_and) | parent_or
all_bits[child] = (old_all & parent_and) | parent_or
lazy_and[child] = new_and
lazy_or[child] = new_or
child = (p << 1) | 1
count_base = child * 30
child_and = lazy_and[child]
child_or = lazy_or[child]
new_and = (child_and & parent_and) | parent_or
new_or = (child_or & parent_and) | parent_or
old_any = any_bits[child]
old_all = all_bits[child]
clear_bits = old_any & (VALUE_MASK ^ parent_and)
set_bits = parent_or & (VALUE_MASK ^ old_all)
changed = clear_bits | set_bits
if changed or new_and != child_and or new_or != child_or:
if not saved[child]:
save_full(child)
value = total[child]
for b in bit_pos_lo[clear_bits & low15]:
index = count_base + b
value -= counts[index] << b
counts[index] = 0
for b in bit_pos_hi[clear_bits >> 15]:
index = count_base + b
value -= counts[index] << b
counts[index] = 0
for b in bit_pos_lo[set_bits & low15]:
index = count_base + b
old_count = counts[index]
value += (half - old_count) << b
counts[index] = half
for b in bit_pos_hi[set_bits >> 15]:
index = count_base + b
old_count = counts[index]
value += (half - old_count) << b
counts[index] = half
total[child] = value
any_bits[child] = (old_any & parent_and) | parent_or
all_bits[child] = (old_all & parent_and) | parent_or
lazy_and[child] = new_and
lazy_or[child] = new_or
lazy_and[p] = VALUE_MASK
lazy_or[p] = 0
def range_and(p, left_bound, length, query_left, query_right, mask,
total=total, counts=counts,
any_bits=any_bits, all_bits=all_bits,
lazy_and=lazy_and, lazy_or=lazy_or,
saved=saved,
bit_pos_lo=bit_pos_lo, bit_pos_hi=bit_pos_hi,
low15=low15, push_nonidentity=push_nonidentity,
save_full=save_full):
if query_left <= left_bound and left_bound + length <= query_right:
changed = any_bits[p] & (VALUE_MASK ^ mask)
if not changed:
return 0
if not saved[p]:
save_full(p)
value = total[p]
count_base = p * 30
for b in bit_pos_lo[changed & low15]:
index = count_base + b
value -= counts[index] << b
counts[index] = 0
for b in bit_pos_hi[changed >> 15]:
index = count_base + b
value -= counts[index] << b
counts[index] = 0
total[p] = value
any_bits[p] &= mask
all_bits[p] &= mask
lazy_and[p] &= mask
lazy_or[p] &= mask
return changed
half = length >> 1
parent_and = lazy_and[p]
parent_or = lazy_or[p]
if parent_and != VALUE_MASK or parent_or:
push_nonidentity(p, half, parent_and, parent_or)
middle = left_bound + half
if query_right <= middle:
changed = range_and(p << 1, left_bound, half,
query_left, query_right, mask)
elif query_left >= middle:
changed = range_and(p << 1 | 1, middle, half,
query_left, query_right, mask)
else:
changed = range_and(p << 1, left_bound, half,
query_left, query_right, mask)
changed |= range_and(p << 1 | 1, middle, half,
query_left, query_right, mask)
if changed:
if not saved[p]:
save_full(p)
left = p << 1
right = left | 1
count_base = p * 30
left_base = left * 30
right_base = right * 30
for b in bit_pos_lo[changed & low15]:
counts[count_base + b] = counts[left_base + b] + counts[right_base + b]
for b in bit_pos_hi[changed >> 15]:
counts[count_base + b] = counts[left_base + b] + counts[right_base + b]
total[p] = total[left] + total[right]
any_bits[p] = any_bits[left] | any_bits[right]
all_bits[p] = all_bits[left] & all_bits[right]
return changed
def range_or(p, left_bound, length, query_left, query_right, mask,
total=total, counts=counts,
any_bits=any_bits, all_bits=all_bits,
lazy_and=lazy_and, lazy_or=lazy_or,
saved=saved,
bit_pos_lo=bit_pos_lo, bit_pos_hi=bit_pos_hi,
low15=low15, push_nonidentity=push_nonidentity,
save_full=save_full):
if query_left <= left_bound and left_bound + length <= query_right:
changed = mask & (VALUE_MASK ^ all_bits[p])
if not changed:
return 0
if not saved[p]:
save_full(p)
value = total[p]
count_base = p * 30
for b in bit_pos_lo[changed & low15]:
index = count_base + b
old_count = counts[index]
value += (length - old_count) << b
counts[index] = length
for b in bit_pos_hi[changed >> 15]:
index = count_base + b
old_count = counts[index]
value += (length - old_count) << b
counts[index] = length
total[p] = value
any_bits[p] |= mask
all_bits[p] |= mask
lazy_and[p] |= mask
lazy_or[p] |= mask
return changed
half = length >> 1
parent_and = lazy_and[p]
parent_or = lazy_or[p]
if parent_and != VALUE_MASK or parent_or:
push_nonidentity(p, half, parent_and, parent_or)
middle = left_bound + half
if query_right <= middle:
changed = range_or(p << 1, left_bound, half,
query_left, query_right, mask)
elif query_left >= middle:
changed = range_or(p << 1 | 1, middle, half,
query_left, query_right, mask)
else:
changed = range_or(p << 1, left_bound, half,
query_left, query_right, mask)
changed |= range_or(p << 1 | 1, middle, half,
query_left, query_right, mask)
if changed:
if not saved[p]:
save_full(p)
left = p << 1
right = left | 1
count_base = p * 30
left_base = left * 30
right_base = right * 30
for b in bit_pos_lo[changed & low15]:
counts[count_base + b] = counts[left_base + b] + counts[right_base + b]
for b in bit_pos_hi[changed >> 15]:
counts[count_base + b] = counts[left_base + b] + counts[right_base + b]
total[p] = total[left] + total[right]
any_bits[p] = any_bits[left] | any_bits[right]
all_bits[p] = all_bits[left] & all_bits[right]
return changed
def range_sum(p, left_bound, length, query_left, query_right,
pending_and=VALUE_MASK, pending_or=0,
total=total, counts=counts,
any_bits=any_bits, all_bits=all_bits,
lazy_and=lazy_and, lazy_or=lazy_or,
bit_pos_lo=bit_pos_lo, bit_pos_hi=bit_pos_hi,
low15=low15):
if query_left <= left_bound and left_bound + length <= query_right:
if pending_and == VALUE_MASK and pending_or == 0:
return total[p]
if pending_and == pending_or:
return length * pending_or
value = total[p]
count_base = p * 30
clear_bits = any_bits[p] & (VALUE_MASK ^ pending_and)
set_bits = pending_or & (VALUE_MASK ^ all_bits[p])
for b in bit_pos_lo[clear_bits & low15]:
value -= counts[count_base + b] << b
for b in bit_pos_hi[clear_bits >> 15]:
value -= counts[count_base + b] << b
for b in bit_pos_lo[set_bits & low15]:
value += (length - counts[count_base + b]) << b
for b in bit_pos_hi[set_bits >> 15]:
value += (length - counts[count_base + b]) << b
return value
node_and = lazy_and[p]
node_or = lazy_or[p]
child_pending_and = (node_and & pending_and) | pending_or
child_pending_or = (node_or & pending_and) | pending_or
half = length >> 1
middle = left_bound + half
if query_right <= middle:
return range_sum(p << 1, left_bound, half,
query_left, query_right,
child_pending_and, child_pending_or)
if query_left >= middle:
return range_sum(p << 1 | 1, middle, half,
query_left, query_right,
child_pending_and, child_pending_or)
return (range_sum(p << 1, left_bound, half,
query_left, query_right,
child_pending_and, child_pending_or) +
range_sum(p << 1 | 1, middle, half,
query_left, query_right,
child_pending_and, child_pending_or))
def begin():
history.clear()
def rollback():
for h in history:
p = h[0]
total[p] = h[1]
any_bits[p] = h[2]
all_bits[p] = h[3]
lazy_and[p] = h[4]
lazy_or[p] = h[5]
count_base = p * 30
counts[count_base:count_base + 30] = h[6]
saved[p] = 0
history.clear()
return size, begin, rollback, range_and, range_or, range_sum
def main():
(n, m, initial, left_data, right_data, mask_data,
sum_left_data, sum_right_data, problem_count,
starts, query_counts) = parse_input()
size, begin, rollback, range_and, range_or, range_sum = build_tree(initial)
output = []
output_append = output.append
write = sys.stdout.write
problem_index = 0
while problem_index < problem_count:
begin()
y = problem_index + 1
query_count = query_counts[problem_index]
z = ((starts[problem_index] + 1) % m) + 1
while query_count:
u = left_data[z] ^ y
if u < 1:
u = 1
elif u > n:
u = n
v = right_data[z] ^ y
if v < 1:
v = 1
elif v > n:
v = n
if u <= v:
update_left = u - 1
update_right = v
else:
update_left = v - 1
update_right = u
u = sum_left_data[z] ^ y
if u < 1:
u = 1
elif u > n:
u = n
v = sum_right_data[z] ^ y
if v < 1:
v = 1
elif v > n:
v = n
if u <= v:
sum_left = u - 1
sum_right = v
else:
sum_left = v - 1
sum_right = u
update_mask = (mask_data[z] ^ y) & VALUE_MASK
if z & 1:
range_and(1, 0, size, update_left, update_right,
update_mask)
else:
range_or(1, 0, size, update_left, update_right,
update_mask)
y = range_sum(1, 0, size, sum_left, sum_right) & VALUE_MASK
z += 1
if z > m:
z = 1
query_count -= 1
output_append(str(y))
rollback()
if len(output) == 4096:
write("\n".join(output) + "\n")
output.clear()
problem_index += 1
if output:
write("\n".join(output) + "\n")
if __name__ == "__main__":
main()