結果

問題 No.749 クエリ全部盛り
ユーザー lam6er
提出日時 2025-03-31 17:52:43
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,940 ms / 3,000 ms
コード長 4,148 bytes
コンパイル時間 225 ms
コンパイル使用メモリ 82,152 KB
実行使用メモリ 225,228 KB
最終ジャッジ日時 2025-03-31 17:53:49
合計ジャッジ時間 13,432 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    ptr = 0
    N = int(data[ptr])
    ptr += 1
    Q = int(data[ptr])
    ptr += 1

    max_fib = N + 3
    F = [0] * (max_fib + 2)
    F[0] = 0
    F[1] = 1
    for i in range(2, max_fib + 2):
        F[i] = (F[i-1] + F[i-2]) % MOD

    S_F = [0] * (max_fib + 3)
    for i in range(1, max_fib + 3):
        S_F[i] = (S_F[i-1] + F[i-1]) % MOD

    class LazySegmentTree:
        def __init__(self, size):
            self.n = size
            self.size = 1
            while self.size < self.n:
                self.size <<= 1
            self.data = [0] * (2 * self.size)
            self.mul = [1] * (2 * self.size)
            self.add_a = [0] * (2 * self.size)
            self.add_b = [0] * (2 * self.size)
            self.add_c = [0] * (2 * self.size)

        def _apply(self, node, l, r, mul_val, add_a_val, add_b_val, add_c_val):
            len_seg = r - l + 1
            sum_F = (S_F[r+1] - S_F[l]) % MOD
            sum_Fp1 = (S_F[r+2] - S_F[l+1]) % MOD
            self.data[node] = (
                mul_val * self.data[node] + 
                add_a_val * len_seg + 
                add_b_val * sum_F + 
                add_c_val * sum_Fp1
            ) % MOD
            current_mul = self.mul[node]
            current_a = self.add_a[node]
            current_b = self.add_b[node]
            current_c = self.add_c[node]
            self.mul[node] = (mul_val * current_mul) % MOD
            self.add_a[node] = (mul_val * current_a + add_a_val) % MOD
            self.add_b[node] = (mul_val * current_b + add_b_val) % MOD
            self.add_c[node] = (mul_val * current_c + add_c_val) % MOD

        def _push(self, node, l, r):
            if (self.mul[node] == 1 and self.add_a[node] == 0 and 
                self.add_b[node] == 0 and self.add_c[node] == 0):
                return
            mid = (l + r) // 2
            left = 2 * node
            self._apply(left, l, mid, self.mul[node], self.add_a[node], self.add_b[node], self.add_c[node])
            right_node = 2 * node + 1
            self._apply(right_node, mid + 1, r, self.mul[node], self.add_a[node], self.add_b[node], self.add_c[node])
            self.mul[node] = 1
            self.add_a[node] = 0
            self.add_b[node] = 0
            self.add_c[node] = 0

        def update_range(self, a, b, mul_val, add_a_val, add_b_val, add_c_val):
            def _update(node, l, r):
                if b < l or r < a:
                    return
                if a <= l and r <= b:
                    self._apply(node, l, r, mul_val, add_a_val, add_b_val, add_c_val)
                    return
                self._push(node, l, r)
                mid = (l + r) // 2
                _update(2 * node, l, mid)
                _update(2 * node + 1, mid + 1, r)
                self.data[node] = (self.data[2 * node] + self.data[2 * node + 1]) % MOD
            _update(1, 0, self.size - 1)

        def query_range(self, a, b):
            res = 0
            def _query(node, l, r):
                nonlocal res
                if b < l or r < a:
                    return
                if a <= l and r <= b:
                    res = (res + self.data[node]) % MOD
                    return
                self._push(node, l, r)
                mid = (l + r) // 2
                _query(2 * node, l, mid)
                _query(2 * node + 1, mid + 1, r)
            _query(1, 0, self.size - 1)
            return res

    seg = LazySegmentTree(N)

    for _ in range(Q):
        q = int(data[ptr])
        ptr += 1
        l = int(data[ptr])
        ptr += 1
        r = int(data[ptr])
        ptr += 1
        k = int(data[ptr])
        ptr += 1
        if q == 0:
            s = seg.query_range(l, r)
            print((s * k) % MOD)
        elif q == 1:
            seg.update_range(l, r, 0, k, 0, 0)
        elif q == 2:
            seg.update_range(l, r, 1, k, 0, 0)
        elif q == 3:
            seg.update_range(l, r, k, 0, 0, 0)
        elif q == 4:
            seg.update_range(l, r, 1, 0, k, 0)

if __name__ == "__main__":
    main()
0