結果
| 問題 | No.3671 Reusable Lazy Segment Tree |
| コンテスト | |
| ユーザー |
 harurun
|
| 提出日時 | 2026-08-05 07:23:13 |
| 言語 | PyPy3 (7.3.23 + ACL) |
| 結果 |
TLE
不安定
|
| 実行時間 | - |
| コード長 | 21,533 bytes |
| 記録 | |
| コンパイル時間 | 255 ms |
| コンパイル使用メモリ | 95,948 KB |
| 実行使用メモリ | 335,496 KB |
| 最終ジャッジ日時 | 2026-09-04 22:03:22 |
| 合計ジャッジ時間 | 15,166 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge3_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 for _ in range(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_epoch = array("I", [0]) * 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
for b in bit_pos_lo[value & low15]:
counts[b][p] = 1
for b in bit_pos_hi[value >> 15]:
counts[b][p] = 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]
node_range = range(size - 1, 0, -1)
for bit_counts in counts:
for p in node_range:
left = p << 1
bit_counts[p] = bit_counts[left] + bit_counts[left | 1]
hist_index = []
hist_total = []
hist_any = []
hist_all = []
hist_lazy_and = []
hist_lazy_or = []
hist_counts = []
hi_append = hist_index.append
ht_append = hist_total.append
ha_append = hist_any.append
hall_append = hist_all.append
hla_append = hist_lazy_and.append
hlo_append = hist_lazy_or.append
hist_count_append = hist_counts.append
def save_full(p, epoch,
total=total, counts=counts,
any_bits=any_bits, all_bits=all_bits,
lazy_and=lazy_and, lazy_or=lazy_or,
saved_epoch=saved_epoch,
hi_append=hi_append, ht_append=ht_append,
ha_append=ha_append, hall_append=hall_append,
hla_append=hla_append, hlo_append=hlo_append,
hist_count_append=hist_count_append):
saved_epoch[p] = epoch
hi_append(p)
ht_append(total[p])
ha_append(any_bits[p])
hall_append(all_bits[p])
hla_append(lazy_and[p])
hlo_append(lazy_or[p])
c0, c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11, c12, c13, c14, c15, c16, c17, c18, c19, c20, c21, c22, c23, c24, c25, c26, c27, c28, c29 = counts
hist_count_append(c0[p])
hist_count_append(c1[p])
hist_count_append(c2[p])
hist_count_append(c3[p])
hist_count_append(c4[p])
hist_count_append(c5[p])
hist_count_append(c6[p])
hist_count_append(c7[p])
hist_count_append(c8[p])
hist_count_append(c9[p])
hist_count_append(c10[p])
hist_count_append(c11[p])
hist_count_append(c12[p])
hist_count_append(c13[p])
hist_count_append(c14[p])
hist_count_append(c15[p])
hist_count_append(c16[p])
hist_count_append(c17[p])
hist_count_append(c18[p])
hist_count_append(c19[p])
hist_count_append(c20[p])
hist_count_append(c21[p])
hist_count_append(c22[p])
hist_count_append(c23[p])
hist_count_append(c24[p])
hist_count_append(c25[p])
hist_count_append(c26[p])
hist_count_append(c27[p])
hist_count_append(c28[p])
hist_count_append(c29[p])
def push_nonidentity(p, half, epoch, 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_epoch=saved_epoch,
bit_pos_lo=bit_pos_lo, bit_pos_hi=bit_pos_hi,
low15=low15, save_full=save_full):
child = p << 1
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 saved_epoch[child] != epoch:
save_full(child, epoch)
value = total[child]
for b in bit_pos_lo[clear_bits & low15]:
bit_counts = counts[b]
value -= bit_counts[child] << b
bit_counts[child] = 0
for b in bit_pos_hi[clear_bits >> 15]:
bit_counts = counts[b]
value -= bit_counts[child] << b
bit_counts[child] = 0
for b in bit_pos_lo[set_bits & low15]:
bit_counts = counts[b]
old_count = bit_counts[child]
value += (half - old_count) << b
bit_counts[child] = half
for b in bit_pos_hi[set_bits >> 15]:
bit_counts = counts[b]
old_count = bit_counts[child]
value += (half - old_count) << b
bit_counts[child] = 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
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 saved_epoch[child] != epoch:
save_full(child, epoch)
value = total[child]
for b in bit_pos_lo[clear_bits & low15]:
bit_counts = counts[b]
value -= bit_counts[child] << b
bit_counts[child] = 0
for b in bit_pos_hi[clear_bits >> 15]:
bit_counts = counts[b]
value -= bit_counts[child] << b
bit_counts[child] = 0
for b in bit_pos_lo[set_bits & low15]:
bit_counts = counts[b]
old_count = bit_counts[child]
value += (half - old_count) << b
bit_counts[child] = half
for b in bit_pos_hi[set_bits >> 15]:
bit_counts = counts[b]
old_count = bit_counts[child]
value += (half - old_count) << b
bit_counts[child] = 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, epoch,
total=total, counts=counts,
any_bits=any_bits, all_bits=all_bits,
lazy_and=lazy_and, lazy_or=lazy_or,
saved_epoch=saved_epoch,
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 saved_epoch[p] != epoch:
save_full(p, epoch)
value = total[p]
for b in bit_pos_lo[changed & low15]:
bit_counts = counts[b]
value -= bit_counts[p] << b
bit_counts[p] = 0
for b in bit_pos_hi[changed >> 15]:
bit_counts = counts[b]
value -= bit_counts[p] << b
bit_counts[p] = 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, epoch, 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, epoch)
elif query_left >= middle:
changed = range_and(p << 1 | 1, middle, half,
query_left, query_right, mask, epoch)
else:
changed = range_and(p << 1, left_bound, half,
query_left, query_right, mask, epoch)
changed |= range_and(p << 1 | 1, middle, half,
query_left, query_right, mask, epoch)
if changed:
if saved_epoch[p] != epoch:
save_full(p, epoch)
left = p << 1
right = left | 1
for b in bit_pos_lo[changed & low15]:
bit_counts = counts[b]
bit_counts[p] = bit_counts[left] + bit_counts[right]
for b in bit_pos_hi[changed >> 15]:
bit_counts = counts[b]
bit_counts[p] = bit_counts[left] + bit_counts[right]
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, epoch,
total=total, counts=counts,
any_bits=any_bits, all_bits=all_bits,
lazy_and=lazy_and, lazy_or=lazy_or,
saved_epoch=saved_epoch,
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 saved_epoch[p] != epoch:
save_full(p, epoch)
value = total[p]
for b in bit_pos_lo[changed & low15]:
bit_counts = counts[b]
old_count = bit_counts[p]
value += (length - old_count) << b
bit_counts[p] = length
for b in bit_pos_hi[changed >> 15]:
bit_counts = counts[b]
old_count = bit_counts[p]
value += (length - old_count) << b
bit_counts[p] = 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, epoch, 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, epoch)
elif query_left >= middle:
changed = range_or(p << 1 | 1, middle, half,
query_left, query_right, mask, epoch)
else:
changed = range_or(p << 1, left_bound, half,
query_left, query_right, mask, epoch)
changed |= range_or(p << 1 | 1, middle, half,
query_left, query_right, mask, epoch)
if changed:
if saved_epoch[p] != epoch:
save_full(p, epoch)
left = p << 1
right = left | 1
for b in bit_pos_lo[changed & low15]:
bit_counts = counts[b]
bit_counts[p] = bit_counts[left] + bit_counts[right]
for b in bit_pos_hi[changed >> 15]:
bit_counts = counts[b]
bit_counts[p] = bit_counts[left] + bit_counts[right]
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]
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[b][p] << b
for b in bit_pos_hi[clear_bits >> 15]:
value -= counts[b][p] << b
for b in bit_pos_lo[set_bits & low15]:
value += (length - counts[b][p]) << b
for b in bit_pos_hi[set_bits >> 15]:
value += (length - counts[b][p]) << 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():
hist_index.clear()
hist_total.clear()
hist_any.clear()
hist_all.clear()
hist_lazy_and.clear()
hist_lazy_or.clear()
hist_counts.clear()
def rollback():
for p, old_total, old_any, old_all, old_and, old_or in zip(
hist_index, hist_total, hist_any, hist_all,
hist_lazy_and, hist_lazy_or):
total[p] = old_total
any_bits[p] = old_any
all_bits[p] = old_all
lazy_and[p] = old_and
lazy_or[p] = old_or
c0, c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11, c12, c13, c14, c15, c16, c17, c18, c19, c20, c21, c22, c23, c24, c25, c26, c27, c28, c29 = counts
k = 0
for p in hist_index:
c0[p] = hist_counts[k + 0]
c1[p] = hist_counts[k + 1]
c2[p] = hist_counts[k + 2]
c3[p] = hist_counts[k + 3]
c4[p] = hist_counts[k + 4]
c5[p] = hist_counts[k + 5]
c6[p] = hist_counts[k + 6]
c7[p] = hist_counts[k + 7]
c8[p] = hist_counts[k + 8]
c9[p] = hist_counts[k + 9]
c10[p] = hist_counts[k + 10]
c11[p] = hist_counts[k + 11]
c12[p] = hist_counts[k + 12]
c13[p] = hist_counts[k + 13]
c14[p] = hist_counts[k + 14]
c15[p] = hist_counts[k + 15]
c16[p] = hist_counts[k + 16]
c17[p] = hist_counts[k + 17]
c18[p] = hist_counts[k + 18]
c19[p] = hist_counts[k + 19]
c20[p] = hist_counts[k + 20]
c21[p] = hist_counts[k + 21]
c22[p] = hist_counts[k + 22]
c23[p] = hist_counts[k + 23]
c24[p] = hist_counts[k + 24]
c25[p] = hist_counts[k + 25]
c26[p] = hist_counts[k + 26]
c27[p] = hist_counts[k + 27]
c28[p] = hist_counts[k + 28]
c29[p] = hist_counts[k + 29]
k += 30
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
epoch = 0
problem_index = 0
while problem_index < problem_count:
epoch += 1
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, epoch)
else:
range_or(1, 0, size, update_left, update_right,
update_mask, epoch)
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()