結果
| 問題 | No.3671 Reusable Lazy Segment Tree |
| コンテスト | |
| ユーザー |
 harurun
|
| 提出日時 | 2026-08-05 14:32:21 |
| 言語 | PyPy3 (7.3.23 + ACL) |
| 結果 |
TLE
不安定
|
| 実行時間 | - |
| コード長 | 51,684 bytes |
| 記録 | |
| コンパイル時間 | 261 ms |
| コンパイル使用メモリ | 96,072 KB |
| 実行使用メモリ | 243,612 KB |
| 最終ジャッジ日時 | 2026-09-04 22:03:45 |
| 合計ジャッジ時間 | 14,986 ms |
|
ジャッジサーバーID （参考情報） |
judge1_1 / judge2_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 10 TLE * 1 -- * 8 |
ソースコード
#!/usr/bin/env python3
from array import array
import sys
BITS = 30
VALUE_MASK = (1 << BITS) - 1
LOW15_MASK = (1 << 15) - 1
def parse_input():
values = list(map(int, sys.stdin.buffer.read().split()))
i = 0
n = values[i]
m = values[i + 1]
i += 2
initial = values[i:i + n]
i += n
left_data = [0] + values[i:i + m]
i += m
right_data = [0] + values[i:i + m]
i += m
mask_data = [0] + values[i:i + m]
i += m
sum_left_data = [0] + values[i:i + m]
i += m
sum_right_data = [0] + values[i:i + m]
i += m
problem_count = values[i]
i += 1
tail = values[i:]
starts = tail[0::2]
counts = tail[1::2]
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
height = size.bit_length() - 1
# Base-B digits are per-bit population counts. B is chosen so that
# evaluating the digit polynomial at 2 via mod (B-2) is exact.
width = (n * VALUE_MASK + 2).bit_length()
base = 1 << width
field_ones = base - 1
eval_mod = base - 2
high_shift = 15 * width
field_mask_lo = [0] * (1 << 15)
digit_all = 0
for bit in range(30):
digit_all |= 1 << (bit * width)
for mask in range(1, 1 << 15):
low = mask & -mask
field_mask_lo[mask] = field_mask_lo[mask ^ low] | (field_ones << ((low.bit_length() - 1) * width))
field_mask_hi = [v << high_shift for v in field_mask_lo]
total = [0] * nodes
packed = [0] * nodes
any_bits = [0] * nodes
all_bits = [0] * nodes
lazy_and = [VALUE_MASK] * nodes
lazy_or = [0] * nodes
saved = bytearray(nodes)
p = size
fmlo = field_mask_lo
fmhi = field_mask_hi
low15 = LOW15_MASK
for value in values:
total[p] = value
packed[p] = (fmlo[value & low15] | fmhi[value >> 15]) & digit_all
any_bits[p] = value
all_bits[p] = value
p += 1
p = size - 1
while p:
left = p << 1
right = left | 1
total[p] = total[left] + total[right]
packed[p] = packed[left] + packed[right]
any_bits[p] = any_bits[left] | any_bits[right]
all_bits[p] = all_bits[left] & all_bits[right]
p -= 1
initial_total = total.copy()
initial_packed = packed.copy()
initial_any = any_bits.copy()
initial_all = all_bits.copy()
history = []
history_append = history.append
def save(p, saved=saved, history_append=history_append):
saved[p] = 1
history_append(p)
def push(p, half, parent_and, parent_or,
total=total, packed=packed, any_bits=any_bits, all_bits=all_bits,
lazy_and=lazy_and, lazy_or=lazy_or, saved=saved, save=save,
fmlo=fmlo, fmhi=fmhi, digit_all=digit_all, low15=low15,
eval_mod=eval_mod):
left = p << 1
right = left | 1
if parent_and == parent_or:
constant = parent_or
constant_field = fmlo[constant & low15] | fmhi[constant >> 15]
constant_packed = (constant_field & digit_all) * half
old_any = any_bits[left]
if old_any != constant or all_bits[left] != constant:
if not saved[left]:
save(left)
total[left] = half * constant
packed[left] = constant_packed
any_bits[left] = constant
all_bits[left] = constant
lazy_and[left] = constant
lazy_or[left] = constant
old_any = any_bits[right]
if old_any != constant or all_bits[right] != constant:
if not saved[right]:
save(right)
total[right] = half * constant
packed[right] = constant_packed
any_bits[right] = constant
all_bits[right] = constant
lazy_and[right] = constant
lazy_or[right] = constant
elif parent_and == VALUE_MASK:
mask = parent_or
old_all = all_bits[left]
changed = mask & (VALUE_MASK ^ old_all)
if changed:
if not saved[left]:
save(left)
field_mask = fmlo[changed & low15] | fmhi[changed >> 15]
digit = field_mask & digit_all
old_packed = packed[left]
total[left] += half * changed - ((old_packed & field_mask) % eval_mod)
packed[left] = (old_packed & ~field_mask) | (digit * half)
any_bits[left] |= mask
all_bits[left] = old_all | mask
lazy_and[left] |= mask
lazy_or[left] |= mask
old_all = all_bits[right]
changed = mask & (VALUE_MASK ^ old_all)
if changed:
if not saved[right]:
save(right)
field_mask = fmlo[changed & low15] | fmhi[changed >> 15]
digit = field_mask & digit_all
old_packed = packed[right]
total[right] += half * changed - ((old_packed & field_mask) % eval_mod)
packed[right] = (old_packed & ~field_mask) | (digit * half)
any_bits[right] |= mask
all_bits[right] = old_all | mask
lazy_and[right] |= mask
lazy_or[right] |= mask
elif parent_or == 0:
mask = parent_and
clear_mask = VALUE_MASK ^ mask
old_any = any_bits[left]
changed = old_any & clear_mask
if changed:
if not saved[left]:
save(left)
field_mask = fmlo[changed & low15] | fmhi[changed >> 15]
old_packed = packed[left]
total[left] -= (old_packed & field_mask) % eval_mod
packed[left] = old_packed & ~field_mask
any_bits[left] = old_any & mask
all_bits[left] &= mask
lazy_and[left] &= mask
lazy_or[left] &= mask
old_any = any_bits[right]
changed = old_any & clear_mask
if changed:
if not saved[right]:
save(right)
field_mask = fmlo[changed & low15] | fmhi[changed >> 15]
old_packed = packed[right]
total[right] -= (old_packed & field_mask) % eval_mod
packed[right] = old_packed & ~field_mask
any_bits[right] = old_any & mask
all_bits[right] &= mask
lazy_and[right] &= mask
lazy_or[right] &= mask
else:
child = left
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:
if not saved[child]:
save(child)
set_field = fmlo[set_bits & low15] | fmhi[set_bits >> 15]
set_digit = set_field & digit_all
field_mask = fmlo[changed & low15] | fmhi[changed >> 15]
old_packed = packed[child]
total[child] += half * set_bits - ((old_packed & field_mask) % eval_mod)
packed[child] = (old_packed & ~field_mask) | (set_digit * half)
any_bits[child] = (old_any & parent_and) | parent_or
all_bits[child] = (old_all & parent_and) | parent_or
lazy_and[child] = (lazy_and[child] & parent_and) | parent_or
lazy_or[child] = (lazy_or[child] & parent_and) | parent_or
child = right
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:
if not saved[child]:
save(child)
set_field = fmlo[set_bits & low15] | fmhi[set_bits >> 15]
set_digit = set_field & digit_all
field_mask = fmlo[changed & low15] | fmhi[changed >> 15]
old_packed = packed[child]
total[child] += half * set_bits - ((old_packed & field_mask) % eval_mod)
packed[child] = (old_packed & ~field_mask) | (set_digit * half)
any_bits[child] = (old_any & parent_and) | parent_or
all_bits[child] = (old_all & parent_and) | parent_or
lazy_and[child] = (lazy_and[child] & parent_and) | parent_or
lazy_or[child] = (lazy_or[child] & parent_and) | parent_or
lazy_and[p] = VALUE_MASK
lazy_or[p] = 0
update_parents = [0] * ((size.bit_length() << 2) + 4)
def range_and(query_left, query_right, mask,
total=total, packed=packed, any_bits=any_bits, all_bits=all_bits,
lazy_and=lazy_and, lazy_or=lazy_or, saved=saved, save=save,
push=push, fmlo=fmlo, fmhi=fmhi, digit_all=digit_all, low15=low15,
size=size, update_parents=update_parents):
clear_mask = VALUE_MASK ^ mask
if not clear_mask:
return
parent_count = 0
p = 1
left_bound = 0
length = size
while True:
changed = any_bits[p] & clear_mask
if not changed:
break
if query_left <= left_bound and left_bound + length <= query_right:
if not saved[p]:
save(p)
field_mask = fmlo[changed & low15] | fmhi[changed >> 15]
old_packed = packed[p]
total[p] -= (old_packed & field_mask) % eval_mod
packed[p] = old_packed & ~field_mask
any_bits[p] &= mask
all_bits[p] &= mask
lazy_and[p] &= mask
lazy_or[p] &= mask
break
half = length >> 1
parent_and = lazy_and[p]
parent_or = lazy_or[p]
if parent_and != VALUE_MASK or parent_or:
push(p, half, parent_and, parent_or)
update_parents[parent_count] = p
parent_count += 1
middle = left_bound + half
if query_right <= middle:
p <<= 1
length = half
continue
if query_left >= middle:
p = p << 1 | 1
left_bound = middle
length = half
continue
# Left suffix [query_left, middle).
branch = p << 1
branch_left = left_bound
branch_length = half
while True:
changed = any_bits[branch] & clear_mask
if not changed:
break
if query_left <= branch_left:
if not saved[branch]:
save(branch)
field_mask = fmlo[changed & low15] | fmhi[changed >> 15]
old_packed = packed[branch]
total[branch] -= (old_packed & field_mask) % eval_mod
packed[branch] = old_packed & ~field_mask
any_bits[branch] &= mask
all_bits[branch] &= mask
lazy_and[branch] &= mask
lazy_or[branch] &= mask
break
branch_half = branch_length >> 1
parent_and = lazy_and[branch]
parent_or = lazy_or[branch]
if parent_and != VALUE_MASK or parent_or:
push(branch, branch_half, parent_and, parent_or)
update_parents[parent_count] = branch
parent_count += 1
branch_middle = branch_left + branch_half
if query_left >= branch_middle:
branch = branch << 1 | 1
branch_left = branch_middle
branch_length = branch_half
else:
sibling = branch << 1 | 1
sibling_changed = any_bits[sibling] & clear_mask
if sibling_changed:
if not saved[sibling]:
save(sibling)
field_mask = fmlo[sibling_changed & low15] | fmhi[sibling_changed >> 15]
old_packed = packed[sibling]
total[sibling] -= (old_packed & field_mask) % eval_mod
packed[sibling] = old_packed & ~field_mask
any_bits[sibling] &= mask
all_bits[sibling] &= mask
lazy_and[sibling] &= mask
lazy_or[sibling] &= mask
branch <<= 1
branch_length = branch_half
# Right prefix [middle, query_right).
branch = p << 1 | 1
branch_left = middle
branch_length = half
while True:
changed = any_bits[branch] & clear_mask
if not changed:
break
if branch_left + branch_length <= query_right:
if not saved[branch]:
save(branch)
field_mask = fmlo[changed & low15] | fmhi[changed >> 15]
old_packed = packed[branch]
total[branch] -= (old_packed & field_mask) % eval_mod
packed[branch] = old_packed & ~field_mask
any_bits[branch] &= mask
all_bits[branch] &= mask
lazy_and[branch] &= mask
lazy_or[branch] &= mask
break
branch_half = branch_length >> 1
parent_and = lazy_and[branch]
parent_or = lazy_or[branch]
if parent_and != VALUE_MASK or parent_or:
push(branch, branch_half, parent_and, parent_or)
update_parents[parent_count] = branch
parent_count += 1
branch_middle = branch_left + branch_half
if query_right <= branch_middle:
branch <<= 1
branch_length = branch_half
else:
sibling = branch << 1
sibling_changed = any_bits[sibling] & clear_mask
if sibling_changed:
if not saved[sibling]:
save(sibling)
field_mask = fmlo[sibling_changed & low15] | fmhi[sibling_changed >> 15]
old_packed = packed[sibling]
total[sibling] -= (old_packed & field_mask) % eval_mod
packed[sibling] = old_packed & ~field_mask
any_bits[sibling] &= mask
all_bits[sibling] &= mask
lazy_and[sibling] &= mask
lazy_or[sibling] &= mask
branch = branch << 1 | 1
branch_left = branch_middle
branch_length = branch_half
break
while parent_count:
parent_count -= 1
p = update_parents[parent_count]
left = p << 1
right = left | 1
new_total = total[left] + total[right]
if new_total != total[p]:
if not saved[p]:
save(p)
total[p] = new_total
packed[p] = packed[left] + packed[right]
any_bits[p] = any_bits[left] | any_bits[right]
all_bits[p] = all_bits[left] & all_bits[right]
def range_or(query_left, query_right, mask,
total=total, packed=packed, any_bits=any_bits, all_bits=all_bits,
lazy_and=lazy_and, lazy_or=lazy_or, saved=saved, save=save,
push=push, fmlo=fmlo, fmhi=fmhi, digit_all=digit_all, low15=low15,
size=size, update_parents=update_parents):
if not mask:
return
parent_count = 0
p = 1
left_bound = 0
length = size
while True:
changed = mask & (VALUE_MASK ^ all_bits[p])
if not changed:
break
if query_left <= left_bound and left_bound + length <= query_right:
if not saved[p]:
save(p)
field_mask = fmlo[changed & low15] | fmhi[changed >> 15]
digit = field_mask & digit_all
old_packed = packed[p]
total[p] += length * changed - ((old_packed & field_mask) % eval_mod)
packed[p] = (old_packed & ~field_mask) | (digit * length)
any_bits[p] |= mask
all_bits[p] |= mask
lazy_and[p] |= mask
lazy_or[p] |= mask
break
half = length >> 1
parent_and = lazy_and[p]
parent_or = lazy_or[p]
if parent_and != VALUE_MASK or parent_or:
push(p, half, parent_and, parent_or)
update_parents[parent_count] = p
parent_count += 1
middle = left_bound + half
if query_right <= middle:
p <<= 1
length = half
continue
if query_left >= middle:
p = p << 1 | 1
left_bound = middle
length = half
continue
branch = p << 1
branch_left = left_bound
branch_length = half
while True:
changed = mask & (VALUE_MASK ^ all_bits[branch])
if not changed:
break
if query_left <= branch_left:
if not saved[branch]:
save(branch)
field_mask = fmlo[changed & low15] | fmhi[changed >> 15]
digit = field_mask & digit_all
old_packed = packed[branch]
total[branch] += branch_length * changed - ((old_packed & field_mask) % eval_mod)
packed[branch] = (old_packed & ~field_mask) | (digit * branch_length)
any_bits[branch] |= mask
all_bits[branch] |= mask
lazy_and[branch] |= mask
lazy_or[branch] |= mask
break
branch_half = branch_length >> 1
parent_and = lazy_and[branch]
parent_or = lazy_or[branch]
if parent_and != VALUE_MASK or parent_or:
push(branch, branch_half, parent_and, parent_or)
update_parents[parent_count] = branch
parent_count += 1
branch_middle = branch_left + branch_half
if query_left >= branch_middle:
branch = branch << 1 | 1
branch_left = branch_middle
branch_length = branch_half
else:
sibling = branch << 1 | 1
sibling_changed = mask & (VALUE_MASK ^ all_bits[sibling])
if sibling_changed:
if not saved[sibling]:
save(sibling)
field_mask = fmlo[sibling_changed & low15] | fmhi[sibling_changed >> 15]
digit = field_mask & digit_all
old_packed = packed[sibling]
total[sibling] += branch_half * sibling_changed - ((old_packed & field_mask) % eval_mod)
packed[sibling] = (old_packed & ~field_mask) | (digit * branch_half)
any_bits[sibling] |= mask
all_bits[sibling] |= mask
lazy_and[sibling] |= mask
lazy_or[sibling] |= mask
branch <<= 1
branch_length = branch_half
branch = p << 1 | 1
branch_left = middle
branch_length = half
while True:
changed = mask & (VALUE_MASK ^ all_bits[branch])
if not changed:
break
if branch_left + branch_length <= query_right:
if not saved[branch]:
save(branch)
field_mask = fmlo[changed & low15] | fmhi[changed >> 15]
digit = field_mask & digit_all
old_packed = packed[branch]
total[branch] += branch_length * changed - ((old_packed & field_mask) % eval_mod)
packed[branch] = (old_packed & ~field_mask) | (digit * branch_length)
any_bits[branch] |= mask
all_bits[branch] |= mask
lazy_and[branch] |= mask
lazy_or[branch] |= mask
break
branch_half = branch_length >> 1
parent_and = lazy_and[branch]
parent_or = lazy_or[branch]
if parent_and != VALUE_MASK or parent_or:
push(branch, branch_half, parent_and, parent_or)
update_parents[parent_count] = branch
parent_count += 1
branch_middle = branch_left + branch_half
if query_right <= branch_middle:
branch <<= 1
branch_length = branch_half
else:
sibling = branch << 1
sibling_changed = mask & (VALUE_MASK ^ all_bits[sibling])
if sibling_changed:
if not saved[sibling]:
save(sibling)
field_mask = fmlo[sibling_changed & low15] | fmhi[sibling_changed >> 15]
digit = field_mask & digit_all
old_packed = packed[sibling]
total[sibling] += branch_half * sibling_changed - ((old_packed & field_mask) % eval_mod)
packed[sibling] = (old_packed & ~field_mask) | (digit * branch_half)
any_bits[sibling] |= mask
all_bits[sibling] |= mask
lazy_and[sibling] |= mask
lazy_or[sibling] |= mask
branch = branch << 1 | 1
branch_left = branch_middle
branch_length = branch_half
break
while parent_count:
parent_count -= 1
p = update_parents[parent_count]
left = p << 1
right = left | 1
new_total = total[left] + total[right]
if new_total != total[p]:
if not saved[p]:
save(p)
total[p] = new_total
packed[p] = packed[left] + packed[right]
any_bits[p] = any_bits[left] | any_bits[right]
all_bits[p] = all_bits[left] & all_bits[right]
def point_and(index, mask,
total=total, packed=packed, any_bits=any_bits, all_bits=all_bits,
lazy_and=lazy_and, lazy_or=lazy_or, saved=saved, save=save,
push=push, fmlo=fmlo, fmhi=fmhi, low15=low15,
eval_mod=eval_mod, size=size, update_parents=update_parents):
clear_mask = VALUE_MASK ^ mask
if not clear_mask:
return
p = 1
left_bound = 0
length = size
parent_count = 0
while length > 1:
if not (any_bits[p] & clear_mask):
return
half = length >> 1
parent_and = lazy_and[p]
parent_or = lazy_or[p]
if parent_and != VALUE_MASK or parent_or:
push(p, half, parent_and, parent_or)
update_parents[parent_count] = p
parent_count += 1
middle = left_bound + half
if index < middle:
p <<= 1
else:
p = p << 1 | 1
left_bound = middle
length = half
changed = any_bits[p] & clear_mask
if not changed:
return
if not saved[p]:
save(p)
new_value = total[p] & mask
total[p] = new_value
packed[p] = (fmlo[new_value & low15] | fmhi[new_value >> 15]) & digit_all
any_bits[p] = new_value
all_bits[p] = new_value
lazy_and[p] = VALUE_MASK
lazy_or[p] = 0
while parent_count:
parent_count -= 1
p = update_parents[parent_count]
left = p << 1
right = left | 1
if not saved[p]:
save(p)
total[p] = total[left] + total[right]
packed[p] = packed[left] + packed[right]
any_bits[p] = any_bits[left] | any_bits[right]
all_bits[p] = all_bits[left] & all_bits[right]
def point_or(index, mask,
total=total, packed=packed, any_bits=any_bits, all_bits=all_bits,
lazy_and=lazy_and, lazy_or=lazy_or, saved=saved, save=save,
push=push, fmlo=fmlo, fmhi=fmhi, digit_all=digit_all, low15=low15,
eval_mod=eval_mod, size=size, update_parents=update_parents):
if not mask:
return
p = 1
left_bound = 0
length = size
parent_count = 0
while length > 1:
if not (mask & (VALUE_MASK ^ all_bits[p])):
return
half = length >> 1
parent_and = lazy_and[p]
parent_or = lazy_or[p]
if parent_and != VALUE_MASK or parent_or:
push(p, half, parent_and, parent_or)
update_parents[parent_count] = p
parent_count += 1
middle = left_bound + half
if index < middle:
p <<= 1
else:
p = p << 1 | 1
left_bound = middle
length = half
changed = mask & (VALUE_MASK ^ all_bits[p])
if not changed:
return
if not saved[p]:
save(p)
new_value = total[p] | mask
total[p] = new_value
packed[p] = (fmlo[new_value & low15] | fmhi[new_value >> 15]) & digit_all
any_bits[p] = new_value
all_bits[p] = new_value
lazy_and[p] = VALUE_MASK
lazy_or[p] = 0
while parent_count:
parent_count -= 1
p = update_parents[parent_count]
left = p << 1
right = left | 1
if not saved[p]:
save(p)
total[p] = total[left] + total[right]
packed[p] = packed[left] + packed[right]
any_bits[p] = any_bits[left] | any_bits[right]
all_bits[p] = all_bits[left] & all_bits[right]
def point_set(index, new_value,
total=total, packed=packed, any_bits=any_bits, all_bits=all_bits,
lazy_and=lazy_and, lazy_or=lazy_or, saved=saved, save=save,
push=push, fmlo=fmlo, fmhi=fmhi, digit_all=digit_all, low15=low15,
height=height):
p = 1
shift = height - 1
while shift >= 0:
parent_and = lazy_and[p]
parent_or = lazy_or[p]
if parent_and != VALUE_MASK or parent_or:
push(p, 1 << shift, parent_and, parent_or)
p = (p << 1) | ((index >> shift) & 1)
shift -= 1
if total[p] == new_value:
return
if not saved[p]:
save(p)
total[p] = new_value
packed[p] = (fmlo[new_value & low15] | fmhi[new_value >> 15]) & digit_all
any_bits[p] = new_value
all_bits[p] = new_value
lazy_and[p] = VALUE_MASK
lazy_or[p] = 0
p >>= 1
while p:
left = p << 1
right = left | 1
if not saved[p]:
save(p)
total[p] = total[left] + total[right]
packed[p] = packed[left] + packed[right]
any_bits[p] = any_bits[left] | any_bits[right]
all_bits[p] = all_bits[left] & all_bits[right]
p >>= 1
def point_and_value(index, mask,
total=total, packed=packed, any_bits=any_bits, all_bits=all_bits,
lazy_and=lazy_and, lazy_or=lazy_or, saved=saved, save=save,
push=push, fmlo=fmlo, fmhi=fmhi, digit_all=digit_all, low15=low15,
height=height):
p = 1
shift = height - 1
while shift >= 0:
parent_and = lazy_and[p]
parent_or = lazy_or[p]
if parent_and != VALUE_MASK or parent_or:
push(p, 1 << shift, parent_and, parent_or)
p = (p << 1) | ((index >> shift) & 1)
shift -= 1
old_value = total[p]
new_value = old_value & mask
if new_value != old_value:
if not saved[p]:
save(p)
total[p] = new_value
packed[p] = (fmlo[new_value & low15] | fmhi[new_value >> 15]) & digit_all
any_bits[p] = new_value
all_bits[p] = new_value
lazy_and[p] = VALUE_MASK
lazy_or[p] = 0
p >>= 1
while p:
left = p << 1
right = left | 1
if not saved[p]:
save(p)
total[p] = total[left] + total[right]
packed[p] = packed[left] + packed[right]
any_bits[p] = any_bits[left] | any_bits[right]
all_bits[p] = all_bits[left] & all_bits[right]
p >>= 1
return new_value
def point_or_value(index, mask,
total=total, packed=packed, any_bits=any_bits, all_bits=all_bits,
lazy_and=lazy_and, lazy_or=lazy_or, saved=saved, save=save,
push=push, fmlo=fmlo, fmhi=fmhi, digit_all=digit_all, low15=low15,
height=height):
p = 1
shift = height - 1
while shift >= 0:
parent_and = lazy_and[p]
parent_or = lazy_or[p]
if parent_and != VALUE_MASK or parent_or:
push(p, 1 << shift, parent_and, parent_or)
p = (p << 1) | ((index >> shift) & 1)
shift -= 1
old_value = total[p]
new_value = old_value | mask
if new_value != old_value:
if not saved[p]:
save(p)
total[p] = new_value
packed[p] = (fmlo[new_value & low15] | fmhi[new_value >> 15]) & digit_all
any_bits[p] = new_value
all_bits[p] = new_value
lazy_and[p] = VALUE_MASK
lazy_or[p] = 0
p >>= 1
while p:
left = p << 1
right = left | 1
if not saved[p]:
save(p)
total[p] = total[left] + total[right]
packed[p] = packed[left] + packed[right]
any_bits[p] = any_bits[left] | any_bits[right]
all_bits[p] = all_bits[left] & all_bits[right]
p >>= 1
return new_value
def point_value(index,
total=total, lazy_and=lazy_and, lazy_or=lazy_or,
size=size):
p = 1
left_bound = 0
length = size
pending_and = VALUE_MASK
pending_or = 0
while length > 1:
node_and = lazy_and[p]
node_or = lazy_or[p]
if pending_and == VALUE_MASK and pending_or == 0:
pending_and = node_and
pending_or = node_or
elif node_and != VALUE_MASK or node_or:
old_pending_and = pending_and
pending_and = (node_and & old_pending_and) | pending_or
pending_or = (node_or & old_pending_and) | pending_or
half = length >> 1
middle = left_bound + half
if index < middle:
p <<= 1
else:
p = p << 1 | 1
left_bound = middle
length = half
return (total[p] & pending_and) | pending_or
def range_sum(query_left, query_right,
total=total, packed=packed, any_bits=any_bits, all_bits=all_bits,
lazy_and=lazy_and, lazy_or=lazy_or,
fmlo=fmlo, fmhi=fmhi, low15=low15,
eval_mod=eval_mod, size=size):
result = 0
p = 1
left_bound = 0
length = size
pending_and = VALUE_MASK
pending_or = 0
while True:
if query_left <= left_bound and left_bound + length <= query_right:
if pending_and == VALUE_MASK and pending_or == 0:
result += total[p]
elif pending_and == pending_or:
result += length * pending_or
else:
clear_bits = any_bits[p] & (VALUE_MASK ^ pending_and)
set_bits = pending_or & (VALUE_MASK ^ all_bits[p])
changed = clear_bits | set_bits
if changed:
field_mask = fmlo[changed & low15] | fmhi[changed >> 15]
result += total[p] + length * set_bits - ((packed[p] & field_mask) % eval_mod)
else:
result += total[p]
return result
node_and = lazy_and[p]
node_or = lazy_or[p]
if pending_and == VALUE_MASK and pending_or == 0:
child_and = node_and
child_or = node_or
elif node_and == VALUE_MASK and node_or == 0:
child_and = pending_and
child_or = pending_or
else:
child_and = (node_and & pending_and) | pending_or
child_or = (node_or & pending_and) | pending_or
half = length >> 1
middle = left_bound + half
if query_right <= middle:
p <<= 1
length = half
pending_and = child_and
pending_or = child_or
continue
if query_left >= middle:
p = p << 1 | 1
left_bound = middle
length = half
pending_and = child_and
pending_or = child_or
continue
# Left suffix [query_left, middle).
branch = p << 1
branch_left = left_bound
branch_length = half
branch_and = child_and
branch_or = child_or
while True:
if query_left <= branch_left:
if branch_and == VALUE_MASK and branch_or == 0:
result += total[branch]
elif branch_and == branch_or:
result += branch_length * branch_or
else:
clear_bits = any_bits[branch] & (VALUE_MASK ^ branch_and)
set_bits = branch_or & (VALUE_MASK ^ all_bits[branch])
changed = clear_bits | set_bits
if changed:
field_mask = fmlo[changed & low15] | fmhi[changed >> 15]
result += total[branch] + branch_length * set_bits - ((packed[branch] & field_mask) % eval_mod)
else:
result += total[branch]
break
node_and = lazy_and[branch]
node_or = lazy_or[branch]
if branch_and == VALUE_MASK and branch_or == 0:
next_and = node_and
next_or = node_or
elif node_and == VALUE_MASK and node_or == 0:
next_and = branch_and
next_or = branch_or
else:
next_and = (node_and & branch_and) | branch_or
next_or = (node_or & branch_and) | branch_or
branch_half = branch_length >> 1
branch_middle = branch_left + branch_half
if query_left >= branch_middle:
branch = branch << 1 | 1
branch_left = branch_middle
branch_length = branch_half
branch_and = next_and
branch_or = next_or
else:
sibling = branch << 1 | 1
if next_and == VALUE_MASK and next_or == 0:
result += total[sibling]
elif next_and == next_or:
result += branch_half * next_or
else:
clear_bits = any_bits[sibling] & (VALUE_MASK ^ next_and)
set_bits = next_or & (VALUE_MASK ^ all_bits[sibling])
changed = clear_bits | set_bits
if changed:
field_mask = fmlo[changed & low15] | fmhi[changed >> 15]
result += total[sibling] + branch_half * set_bits - ((packed[sibling] & field_mask) % eval_mod)
else:
result += total[sibling]
branch <<= 1
branch_length = branch_half
branch_and = next_and
branch_or = next_or
# Right prefix [middle, query_right).
branch = p << 1 | 1
branch_left = middle
branch_length = half
branch_and = child_and
branch_or = child_or
while True:
if branch_left + branch_length <= query_right:
if branch_and == VALUE_MASK and branch_or == 0:
result += total[branch]
elif branch_and == branch_or:
result += branch_length * branch_or
else:
clear_bits = any_bits[branch] & (VALUE_MASK ^ branch_and)
set_bits = branch_or & (VALUE_MASK ^ all_bits[branch])
changed = clear_bits | set_bits
if changed:
field_mask = fmlo[changed & low15] | fmhi[changed >> 15]
result += total[branch] + branch_length * set_bits - ((packed[branch] & field_mask) % eval_mod)
else:
result += total[branch]
break
node_and = lazy_and[branch]
node_or = lazy_or[branch]
if branch_and == VALUE_MASK and branch_or == 0:
next_and = node_and
next_or = node_or
elif node_and == VALUE_MASK and node_or == 0:
next_and = branch_and
next_or = branch_or
else:
next_and = (node_and & branch_and) | branch_or
next_or = (node_or & branch_and) | branch_or
branch_half = branch_length >> 1
branch_middle = branch_left + branch_half
if query_right <= branch_middle:
branch <<= 1
branch_length = branch_half
branch_and = next_and
branch_or = next_or
else:
sibling = branch << 1
if next_and == VALUE_MASK and next_or == 0:
result += total[sibling]
elif next_and == next_or:
result += branch_half * next_or
else:
clear_bits = any_bits[sibling] & (VALUE_MASK ^ next_and)
set_bits = next_or & (VALUE_MASK ^ all_bits[sibling])
changed = clear_bits | set_bits
if changed:
field_mask = fmlo[changed & low15] | fmhi[changed >> 15]
result += total[sibling] + branch_half * set_bits - ((packed[sibling] & field_mask) % eval_mod)
else:
result += total[sibling]
branch = branch << 1 | 1
branch_left = branch_middle
branch_length = branch_half
branch_and = next_and
branch_or = next_or
return result
def begin():
history.clear()
def rollback(total=total, packed=packed, any_bits=any_bits, all_bits=all_bits,
lazy_and=lazy_and, lazy_or=lazy_or, saved=saved,
initial_total=initial_total, initial_packed=initial_packed,
initial_any=initial_any, initial_all=initial_all,
history=history):
for p in history:
total[p] = initial_total[p]
packed[p] = initial_packed[p]
any_bits[p] = initial_any[p]
all_bits[p] = initial_all[p]
lazy_and[p] = VALUE_MASK
lazy_or[p] = 0
saved[p] = 0
history.clear()
return (size, begin, rollback, point_set, point_value,
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, point_set, point_value,
range_and, range_or, range_sum) = build_tree(initial)
# Multi-point overlay storage. The overwhelmingly common one-point case
# stays entirely in scalar locals and never touches this dictionary/Fenwick tree.
pending = {}
fenwick = [0] * (n + 1)
fenwick_seen = bytearray(n + 1)
fenwick_touched = []
fenwick_touched_append = fenwick_touched.append
pending_limit = 64
def fenwick_add(index, delta,
fenwick=fenwick, fenwick_seen=fenwick_seen,
fenwick_touched_append=fenwick_touched_append, n=n):
index += 1
while index <= n:
if not fenwick_seen[index]:
fenwick_seen[index] = 1
fenwick_touched_append(index)
fenwick[index] += delta
index += index & -index
def fenwick_range(left, right, fenwick=fenwick):
a = 0
i = left
while i:
a += fenwick[i]
i &= i - 1
b = 0
i = right
while i:
b += fenwick[i]
i &= i - 1
return b - a
def clear_multi(pending=pending, fenwick=fenwick,
fenwick_seen=fenwick_seen, fenwick_touched=fenwick_touched):
pending.clear()
for i in fenwick_touched:
fenwick[i] = 0
fenwick_seen[i] = 0
fenwick_touched.clear()
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
multi = False
single_index = -1
single_base = 0
single_value = 0
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 update_right - update_left == 1:
index = update_left
if not multi:
if index == single_index:
old_value = single_value
elif single_index < 0:
base_value = point_value(index)
single_index = index
single_base = base_value
single_value = base_value
old_value = base_value
else:
pair = [single_base, single_value]
pending[single_index] = pair
delta = single_value - single_base
if delta:
fenwick_add(single_index, delta)
multi = True
base_value = point_value(index)
pair = [base_value, base_value]
pending[index] = pair
old_value = base_value
if z & 1:
new_value = old_value & update_mask
else:
new_value = old_value | update_mask
if new_value != old_value:
if multi:
pair[1] = new_value
fenwick_add(index, new_value - old_value)
else:
single_value = new_value
else:
pair = pending.get(index)
if pair is None:
if len(pending) >= pending_limit:
for flush_index, flush_pair in pending.items():
point_set(flush_index, flush_pair[1])
clear_multi()
multi = False
base_value = point_value(index)
single_index = index
single_base = base_value
single_value = base_value
old_value = base_value
if z & 1:
new_value = old_value & update_mask
else:
new_value = old_value | update_mask
if new_value != old_value:
single_value = new_value
else:
base_value = point_value(index)
pair = [base_value, base_value]
pending[index] = pair
old_value = base_value
if z & 1:
new_value = old_value & update_mask
else:
new_value = old_value | update_mask
if new_value != old_value:
pair[1] = new_value
fenwick_add(index, new_value - old_value)
else:
old_value = pair[1]
if z & 1:
new_value = old_value & update_mask
else:
new_value = old_value | update_mask
if new_value != old_value:
pair[1] = new_value
fenwick_add(index, new_value - old_value)
else:
if z & 1:
range_and(update_left, update_right, update_mask)
if multi:
for index, pair in pending.items():
if update_left <= index < update_right:
old_base = pair[0]
old_value = pair[1]
new_base = old_base & update_mask
new_value = old_value & update_mask
if new_base != old_base or new_value != old_value:
pair[0] = new_base
pair[1] = new_value
delta_change = (new_value - new_base) - (old_value - old_base)
if delta_change:
fenwick_add(index, delta_change)
elif single_index >= 0 and update_left <= single_index < update_right:
single_base &= update_mask
single_value &= update_mask
else:
range_or(update_left, update_right, update_mask)
if multi:
for index, pair in pending.items():
if update_left <= index < update_right:
old_base = pair[0]
old_value = pair[1]
new_base = old_base | update_mask
new_value = old_value | update_mask
if new_base != old_base or new_value != old_value:
pair[0] = new_base
pair[1] = new_value
delta_change = (new_value - new_base) - (old_value - old_base)
if delta_change:
fenwick_add(index, delta_change)
elif single_index >= 0 and update_left <= single_index < update_right:
single_base |= update_mask
single_value |= update_mask
if sum_right - sum_left == 1:
if multi:
pair = pending.get(sum_left)
if pair is None:
y = point_value(sum_left) & VALUE_MASK
else:
y = pair[1] & VALUE_MASK
elif sum_left == single_index:
y = single_value & VALUE_MASK
else:
y = point_value(sum_left) & VALUE_MASK
else:
y = range_sum(sum_left, sum_right)
if multi:
y += fenwick_range(sum_left, sum_right)
elif single_index >= sum_left and single_index < sum_right:
y += single_value - single_base
y &= VALUE_MASK
z += 1
if z > m:
z = 1
query_count -= 1
if multi:
clear_multi()
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()