#1175006 (PyPy3) No.3671 Reusable Lazy Segment Tree

• 問題: No.3671 Reusable Lazy Segment Tree
• ユーザー: harurun
• 提出日時: 2026-08-05 06:55:36
• 言語: PyPy3 (7.3.23 + ACL)
• 結果: TLE
• 実行時間: -
• コード長: 11,967 bytes
• コンパイル時間: 255 ms
• コンパイル使用メモリ: 95,824 KB
• 実行使用メモリ: 100,572 KB
• 最終ジャッジ日時: 2026-09-04 22:03:07
• 合計ジャッジ時間: 14,610 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_1

ファイルパターン	結果
sample	AC * 1
other	AC * 8 TLE * 1 -- * 10

ソースコード

#!/usr/bin/env python3
import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')
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()