区間クエリ：Lazy Segment Tree

区間クエリ系、第四弾。Lazy Segment Tree（通称：遅延セグ木）です。

仕組みについては、外部記事をたくさん読んでください。めちゃめちゃむずいです。
通常の Segment Tree では更新が１点のみしかできませんが、Lazy Segment Tree では区間の更新が Segment Tree と同等の計算量でできます。

そのほか初期化や、区間クエリに対する計算量は Segment Tree と同じです。

スクリプトはこちら。長いです。

class LazySegmentationTree:

    def __init__(self, l, e_ss, op_ss, e_sl, op_sl, op_ll, propagater):
        n = len(l)
        assert n > 1 and n & (n - 1) == 0
        self.n = n
        self.depth = int.bit_length(n)
        self.e_ss = e_ss
        self.op_ss = op_ss
        self.seg = [e_ss for _ in range(2 * n)]

        self.e_sl = e_sl
        self.op_sl = op_sl
        self.op_ll = op_ll
        self.lazy = [e_sl for _ in range(2 * n)]

        self.propagater = propagater

        for i, li in enumerate(l):
            self.seg[i + n] = li

        for i in range(n - 1, 0, -1):
            self.seg[i] = self.op_ss(self.seg[2 * i], self.seg[2 * i + 1])

    def _propagate(self, left, right):
        for i in range(self.depth - 1, 0, -1):
            l = left >> i
            r = right >> i
            propagetee = self.propagater(self.lazy[l])
            ll = 2 * l
            lr = ll + 1
            self.lazy[ll] = self.op_ll(self.lazy[ll], propagetee)
            self.lazy[lr] = self.op_ll(self.lazy[lr], propagetee)
            self.lazy[l] = self.e_sl
            if l == r:
                continue
            propagetee = self.propagater(self.lazy[r])
            rl = 2 * r
            rr = rl + 1
            self.lazy[rl] = self.op_ll(self.lazy[rl], propagetee)
            self.lazy[rr] = self.op_ll(self.lazy[rr], propagetee)
            self.lazy[r] = self.e_sl

    def _calc(self, left, right):
        for i in range(1, self.depth):
            l = left >> i
            r = right >> i
            ll = 2 * l
            lr = ll + 1
            self.seg[l] = self.op_ss(
                self.op_sl(self.seg[ll], self.lazy[ll]),
                self.op_sl(self.seg[lr], self.lazy[lr])
            )
            if l == r:
                continue
            rl = 2 * r
            rr = rl + 1
            self.seg[r] = self.op_ss(
                self.op_sl(self.seg[rl], self.lazy[rl]),
                self.op_sl(self.seg[rr], self.lazy[rr])
            )

    def _operate(self, left, right, v):
        for _ in range(self.depth - 1):
            if left & 1:
                self.lazy[left] = self.op_ll(self.lazy[left], v)
                left += 1
            if right & 1:
                right -= 1
                self.lazy[right] = self.op_ll(self.lazy[right], v)
            v = self.op_ll(v, v)
            left >>= 1
            right >>= 1
            if left == right:
                break

    def _query(self, left, right):
        res_l, res_r = self.e_ss, self.e_ss
        for _ in range(self.depth - 1):
            if left & 1:
                res_l = self.op_ss(
                    res_l,
                    self.op_sl(self.seg[left], self.lazy[left])
                )
                left += 1
            if right & 1:
                right -= 1
                res_r = self.op_ss(
                    self.op_sl(self.seg[right], self.lazy[right]),
                    res_r
                )
            left >>= 1
            right >>= 1
            if left == right:
                break
        return self.op_ss(res_l, res_r)

    def operate(self, left, right, v):
        assert 0 <= left < self.n and 0 < right <= self.n and left < right
        left += self.n
        right += self.n

        self._propagate(left, right)
        self._operate(left, right, v)
        self._calc(left, right)

    def query(self, left, right):
        assert 0 <= left < self.n and 0 < right <= self.n and left < right
        left += self.n
        right += self.n

        self._propagate(left, right)
        self._calc(left, right)

        return self._query(left, right)

ACL Practice Contest で L - Lazy Segment Tree を通した時の提出回答がこちら。なんかコメントで「解けてない」とか言ってますけど、解けてます。

使ってみた所感としては、PyPy じゃないと間に合わないとか、個々の問題に合わせてチューニングが必要かもしれないとかありますので、ぜひお使いの際はカスタマイズしてお使いください。