結果
| 問題 | No.3671 Reusable Lazy Segment Tree |
| コンテスト | |
| ユーザー |
 harurun
|
| 提出日時 | 2026-08-05 03:43:53 |
| 言語 | PyPy3 (7.3.23 + ACL) |
| 結果 |
TLE
不安定
|
| 実行時間 | - |
| コード長 | 11,907 bytes |
| 記録 | |
| コンパイル時間 | 255 ms |
| コンパイル使用メモリ | 95,944 KB |
| 実行使用メモリ | 103,136 KB |
| 最終ジャッジ日時 | 2026-09-04 22:02:52 |
| 合計ジャッジ時間 | 13,406 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge2_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 8 TLE * 1 -- * 10 |
ソースコード
#!/usr/bin/env python3
from array import array
import sys
BITS = 30
VALUE_MASK = (1 << BITS) - 1
class FastScanner:
__slots__ = ("data", "index", "length")
def __init__(self) -> None:
self.data = sys.stdin.buffer.read()
self.index = 0
self.length = len(self.data)
def int(self) -> int:
data = self.data
n = self.length
i = self.index
while i < n and data[i] <= 32:
i += 1
value = 0
while i < n and data[i] > 32:
value = value * 10 + data[i] - 48
i += 1
self.index = i
return value
class RollbackLazySegTree:
"""Undo付き30-bit AND/OR lazy segment tree.
Pythonの整数オブジェクトをノードごとに持つとメモリが大きいため、
本体はarrayモジュールの固定幅整数配列で保持する。
"""
__slots__ = (
"n", "size", "nodes", "total", "cnt", "any", "all",
"lazy_and", "lazy_or", "saved_epoch", "saved_count_mask", "epoch",
"hist_index", "hist_total", "hist_any", "hist_all",
"hist_lazy_and", "hist_lazy_or",
"hist_count_p", "hist_count_b", "hist_count_value",
)
def __init__(self, values: array) -> None:
self.n = len(values)
size = 1
while size < self.n:
size <<= 1
self.size = size
self.nodes = size << 1
nodes = self.nodes
self.total = array("Q", [0]) * nodes
self.cnt = [array("I", [0]) * nodes for _ in range(BITS)]
self.any = array("I", [0]) * nodes
self.all = array("I", [0]) * nodes
self.lazy_and = array("I", [VALUE_MASK]) * nodes
self.lazy_or = array("I", [0]) * nodes
self.saved_epoch = array("I", [0]) * nodes
self.saved_count_mask = array("I", [0]) * nodes
self.epoch = 0
base = size
for i, value in enumerate(values):
p = base + i
self.total[p] = value
self.any[p] = value
self.all[p] = value
bits = value
while bits:
low = bits & -bits
b = low.bit_length() - 1
self.cnt[b][p] = 1
bits -= low
total = self.total
any_bits = self.any
all_bits = self.all
cnt = self.cnt
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]
for b in range(BITS):
cnt[b][p] = cnt[b][left] + cnt[b][right]
self.hist_index = []
self.hist_total = []
self.hist_any = []
self.hist_all = []
self.hist_lazy_and = []
self.hist_lazy_or = []
self.hist_count_p = []
self.hist_count_b = []
self.hist_count_value = []
def begin_subproblem(self) -> None:
self.epoch += 1
self.hist_index.clear()
self.hist_total.clear()
self.hist_any.clear()
self.hist_all.clear()
self.hist_lazy_and.clear()
self.hist_lazy_or.clear()
self.hist_count_p.clear()
self.hist_count_b.clear()
self.hist_count_value.clear()
def _save(self, p: int, changed_bits: int) -> None:
if self.saved_epoch[p] != self.epoch:
self.saved_epoch[p] = self.epoch
self.saved_count_mask[p] = 0
self.hist_index.append(p)
self.hist_total.append(self.total[p])
self.hist_any.append(self.any[p])
self.hist_all.append(self.all[p])
self.hist_lazy_and.append(self.lazy_and[p])
self.hist_lazy_or.append(self.lazy_or[p])
new_bits = changed_bits & (VALUE_MASK ^ self.saved_count_mask[p])
if new_bits:
self.saved_count_mask[p] |= new_bits
while new_bits:
low = new_bits & -new_bits
b = low.bit_length() - 1
self.hist_count_p.append(p)
self.hist_count_b.append(b)
self.hist_count_value.append(self.cnt[b][p])
new_bits -= low
def rollback(self) -> None:
for k, p in enumerate(self.hist_index):
self.total[p] = self.hist_total[k]
self.any[p] = self.hist_any[k]
self.all[p] = self.hist_all[k]
self.lazy_and[p] = self.hist_lazy_and[k]
self.lazy_or[p] = self.hist_lazy_or[k]
for k, p in enumerate(self.hist_count_p):
self.cnt[self.hist_count_b[k]][p] = self.hist_count_value[k]
def _apply_or(self, p: int, length: int, mask: int) -> int:
changed = mask & (VALUE_MASK ^ self.all[p])
if changed == 0:
return 0
self._save(p, changed)
bits = changed
while bits:
low = bits & -bits
b = low.bit_length() - 1
old_count = self.cnt[b][p]
self.total[p] += (length - old_count) << b
self.cnt[b][p] = length
bits -= low
self.any[p] |= mask
self.all[p] |= mask
self.lazy_or[p] |= mask
return changed
def _apply_and(self, p: int, mask: int) -> int:
changed = self.any[p] & (VALUE_MASK ^ mask)
if changed == 0:
return 0
self._save(p, changed)
bits = changed
while bits:
low = bits & -bits
b = low.bit_length() - 1
old_count = self.cnt[b][p]
self.total[p] -= old_count << b
self.cnt[b][p] = 0
bits -= low
self.any[p] &= mask
self.all[p] &= mask
self.lazy_and[p] &= mask
self.lazy_or[p] &= mask
return changed
def _push(self, p: int, left_bound: int, right_bound: int) -> None:
lazy_and = self.lazy_and[p]
lazy_or = self.lazy_or[p]
if left_bound == right_bound or (lazy_and == VALUE_MASK and lazy_or == 0):
return
mid = (left_bound + right_bound) >> 1
left = p << 1
right = left | 1
self._apply_and(left, lazy_and)
self._apply_or(left, mid - left_bound + 1, lazy_or)
self._apply_and(right, lazy_and)
self._apply_or(right, right_bound - mid, lazy_or)
self._save(p, 0)
self.lazy_and[p] = VALUE_MASK
self.lazy_or[p] = 0
def _pull_changed(self, p: int, length: int, changed: int) -> None:
if changed == 0:
return
self._save(p, changed)
left = p << 1
right = left | 1
bits = changed
while bits:
low = bits & -bits
b = low.bit_length() - 1
old_count = self.cnt[b][p]
new_count = self.cnt[b][left] + self.cnt[b][right]
self.total[p] += (new_count - old_count) << b
self.cnt[b][p] = new_count
if new_count == 0:
self.any[p] &= VALUE_MASK ^ low
else:
self.any[p] |= low
if new_count == length:
self.all[p] |= low
else:
self.all[p] &= VALUE_MASK ^ low
bits -= low
def _range_or(self, p: int, left_bound: int, right_bound: int,
query_left: int, query_right: int, mask: int) -> int:
if query_right < left_bound or right_bound < query_left:
return 0
if (mask & (VALUE_MASK ^ self.all[p])) == 0:
return 0
if query_left <= left_bound and right_bound <= query_right:
return self._apply_or(p, right_bound - left_bound + 1, mask)
self._push(p, left_bound, right_bound)
mid = (left_bound + right_bound) >> 1
changed = self._range_or(p << 1, left_bound, mid, query_left, query_right, mask)
changed |= self._range_or(p << 1 | 1, mid + 1, right_bound,
query_left, query_right, mask)
self._pull_changed(p, right_bound - left_bound + 1, changed)
return changed
def _range_and(self, p: int, left_bound: int, right_bound: int,
query_left: int, query_right: int, mask: int) -> int:
if query_right < left_bound or right_bound < query_left:
return 0
if (self.any[p] & (VALUE_MASK ^ mask)) == 0:
return 0
if query_left <= left_bound and right_bound <= query_right:
return self._apply_and(p, mask)
self._push(p, left_bound, right_bound)
mid = (left_bound + right_bound) >> 1
changed = self._range_and(p << 1, left_bound, mid, query_left, query_right, mask)
changed |= self._range_and(p << 1 | 1, mid + 1, right_bound,
query_left, query_right, mask)
self._pull_changed(p, right_bound - left_bound + 1, changed)
return changed
def _range_sum(self, p: int, left_bound: int, right_bound: int,
query_left: int, query_right: int) -> int:
if query_right < left_bound or right_bound < query_left:
return 0
if query_left <= left_bound and right_bound <= query_right:
return self.total[p]
self._push(p, left_bound, right_bound)
mid = (left_bound + right_bound) >> 1
return self._range_sum(p << 1, left_bound, mid, query_left, query_right) + \
self._range_sum(p << 1 | 1, mid + 1, right_bound, query_left, query_right)
def range_or(self, left: int, right: int, mask: int) -> None:
self._range_or(1, 0, self.size - 1, left, right, mask)
def range_and(self, left: int, right: int, mask: int) -> None:
self._range_and(1, 0, self.size - 1, left, right, mask)
def range_sum(self, left: int, right: int) -> int:
return self._range_sum(1, 0, self.size - 1, left, right)
def read_u32_array(scanner: FastScanner, length: int, leading_zero: bool) -> array:
result = array("I", [0]) * (length + (1 if leading_zero else 0))
offset = 1 if leading_zero else 0
for i in range(length):
result[i + offset] = scanner.int()
return result
def clamp_index(value: int, n: int) -> int:
if value < 1:
return 1
if value > n:
return n
return value
def main() -> None:
scanner = FastScanner()
n = scanner.int()
m = scanner.int()
initial = read_u32_array(scanner, n, False)
l = read_u32_array(scanner, m, True)
r = read_u32_array(scanner, m, True)
x = read_u32_array(scanner, m, True)
big_l = read_u32_array(scanner, m, True)
big_r = read_u32_array(scanner, m, True)
seg = RollbackLazySegTree(initial)
q_count = scanner.int()
output = []
write = sys.stdout.write
for problem_index in range(1, q_count + 1):
s = scanner.int()
query_count = scanner.int()
y = problem_index
seg.begin_subproblem()
for j in range(1, query_count + 1):
z = ((s + j) % m) + 1
u = clamp_index(l[z] ^ y, n)
v = clamp_index(r[z] ^ y, n)
update_left = min(u, v) - 1
update_right = max(u, v) - 1
U = clamp_index(big_l[z] ^ y, n)
V = clamp_index(big_r[z] ^ y, n)
sum_left = min(U, V) - 1
sum_right = max(U, V) - 1
update_mask = x[z] ^ y
if z & 1:
seg.range_and(update_left, update_right, update_mask)
else:
seg.range_or(update_left, update_right, update_mask)
y = seg.range_sum(sum_left, sum_right) & VALUE_MASK
output.append(str(y))
seg.rollback()
if len(output) == 4096:
write("\n".join(output) + "\n")
output.clear()
if output:
write("\n".join(output) + "\n")
if __name__ == "__main__":
main()