結果

問題 No.2901 Logical Sum of Substring
コンテスト
ユーザー hahho
提出日時 2024-05-12 12:14:38
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,721 ms / 3,000 ms
コード長 6,174 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 204 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 307,228 KB
最終ジャッジ日時 2024-09-20 20:51:43
合計ジャッジ時間 39,804 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from typing import *

Self = TypeVar('Self', bound='Monoid')


class Monoid:
    @classmethod
    def identity(cls: Type[Self]) -> Self:
        pass

    def act_on_left(self: Self, other: Self) -> Self:
        pass

    def act_on_right(self: Self, other: Self) -> Self:
        pass

    def copy_to(self: Self, other: Self):
        pass


M = TypeVar('M', bound='Monoid')


class SegmentTree(Generic[M]):
    @classmethod
    def from_initial_data(cls, monoid: Type[M], data: MutableSequence[M]) -> 'SegmentTree[M]':
        size = 1 << (len(data) - 1).bit_length()
        temp = [monoid.identity() for _ in range(2 * size)]
        temp[size:size + len(data)] = data
        data = temp

        for i in reversed(range(1, size)):
            data[2 * i].copy_to(data[i])
            data[i].act_on_right(data[2 * i + 1])
        return cls(monoid, data)

    # これ使わずファクトリーメソッド使いましょうね
    def __init__(self, monoid: Type[M], data: MutableSequence[M]):
        self.monoid = monoid
        self.data = data
        self.size = len(data) // 2

    def reduce(self, l: int, r: int) -> M:
        l += self.size
        r += self.size
        vl = self.monoid.identity()
        vr = self.monoid.identity()

        while l < r:
            if l & 1:
                vl.act_on_right(self.data[l])
                l += 1
            if r & 1:
                r -= 1
                vr.act_on_left(self.data[r])
            l >>= 1
            r >>= 1
        vl.act_on_right(vr)
        return vl

    def get(self, l: int = -1, r: int = -1) -> M:
        return self.reduce(l if l >= 0 else 0, r if r >= 0 else self.size)

    def __getitem__(self, i: int) -> M:
        return self.data[i + self.size]

    def __setitem__(self, i: int, v: M):
        i += self.size
        while i:
            v.copy_to(self.data[i])
            if i & 1:
                v.act_on_left(self.data[i ^ 1])
            else:
                v.act_on_right(self.data[i ^ 1])
            i >>= 1

    def __iter__(self) -> Iterator[M]:
        return iter(self.data[self.size:])


def min2(x, y):
    return x if x < y else y


INF = 2 ** 60


def solve(k, aa, queries):
    MASK = (1 << k) - 1

    class R(Monoid):
        def __init__(self, prefix, suffix, opt, block):
            self.prefix = prefix
            self.suffix = suffix
            self.opt = opt
            self.block = block

        @classmethod
        def identity(cls: Type[Self]) -> Self:
            return R([(0, 0)], [(0, 0)], INF, 0)

        @classmethod
        def single(cls: Type[Self], v: int) -> Self:
            return R([(0, 0), (v, 1)] if v != 0 else [(0, 0)],
                     [(0, 0), (v, 1)] if v != 0 else [(0, 0)],
                     1 if v == MASK else INF,
                     1)

        def act_on_left(self: Self, other: Self) -> Self:

            opt = min2(self.opt, other.opt)
            i = 0
            for v, l in reversed(self.prefix):
                while i < len(other.suffix) and other.suffix[i][0] | v != MASK:
                    i += 1
                if i >= len(other.suffix):
                    break
                opt = min2(opt, l + other.suffix[i][1])
            self.opt = opt

            if other.prefix[-1][0] == MASK:
                self.prefix.clear()
                self.prefix.extend(other.prefix)
            else:
                temp = self.prefix[:]
                self.prefix.clear()
                self.prefix.extend(other.prefix)
                for v, l in temp:
                    u = v | self.prefix[-1][0]
                    if u != self.prefix[-1][0]:
                        self.prefix.append((u, l + other.block))

            if self.suffix[-1][0] != MASK:
                for v, l in other.suffix:
                    u = v | self.suffix[-1][0]
                    if u != self.suffix[-1][0]:
                        self.suffix.append((u, l + self.block))

            self.block += other.block
            return self

        def act_on_right(self: Self, other: Self) -> Self:
            opt = min2(other.opt, self.opt)
            i = 0
            for v, l in reversed(other.prefix):
                while i < len(self.suffix) and self.suffix[i][0] | v != MASK:
                    i += 1
                if i >= len(self.suffix):
                    break
                opt = min2(opt, l + self.suffix[i][1])

            self.opt = opt

            if other.suffix[-1][0] == MASK:
                self.suffix.clear()
                self.suffix.extend(other.suffix)
            else:
                temp = self.suffix[:]
                self.suffix.clear()
                self.suffix.extend(other.suffix)
                for v, l in temp:
                    u = v | self.suffix[-1][0]
                    if u != self.suffix[-1][0]:
                        self.suffix.append((u, l + other.block))

            if self.prefix[-1][0] != MASK:
                for v, l in other.prefix:
                    u = v | self.prefix[-1][0]
                    if u != self.prefix[-1][0]:
                        self.prefix.append((u, l + self.block))

            self.block += other.block
            return other

        def copy_to(self: Self, other: Self):
            other.prefix.clear()
            other.prefix.extend(self.prefix)
            other.suffix.clear()
            other.suffix.extend(self.suffix)
            other.opt = self.opt
            other.block = self.block

    seg = SegmentTree.from_initial_data(monoid=R,
                                        data=[R.single(v) for v in aa]
                                        )

    res = []
    for query in queries:
        mode, *tokens = query
        if mode == 1:
            i, v = tokens
            seg[i] = R.single(v)
        else:
            l, r = tokens
            p = seg.get(l, r).opt
            res.append(p if p < INF else -1)
    return res


n, k = map(int, input().split())
aa = list(map(int, input().split()))
q = int(input())
queries = []
for _ in range(q):
    a, b, c = map(int, input().split())
    queries.append((a, b - 1, c))
print(*solve(k, aa, queries), sep='\n')
0