結果

問題 No.749 クエリ全部盛り
ユーザー toyuzukotoyuzuko
提出日時 2020-05-12 21:53:26
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,478 bytes
コンパイル時間 388 ms
コンパイル使用メモリ 82,324 KB
実行使用メモリ 489,076 KB
最終ジャッジ日時 2024-09-14 00:10:53
合計ジャッジ時間 8,676 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
60,100 KB
testcase_01 AC 39 ms
54,664 KB
testcase_02 AC 39 ms
53,020 KB
testcase_03 AC 38 ms
53,848 KB
testcase_04 AC 38 ms
53,668 KB
testcase_05 AC 151 ms
78,384 KB
testcase_06 AC 149 ms
77,936 KB
testcase_07 AC 159 ms
78,504 KB
testcase_08 AC 147 ms
78,032 KB
testcase_09 AC 158 ms
78,420 KB
testcase_10 AC 503 ms
95,844 KB
testcase_11 AC 483 ms
95,912 KB
testcase_12 AC 491 ms
95,244 KB
testcase_13 AC 493 ms
95,380 KB
testcase_14 AC 501 ms
95,524 KB
testcase_15 TLE -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

class SegmentTreeLazy():
    def __init__(self, arr, ti, ei, func, op, merge):
        self.h = (len(arr) - 1).bit_length()
        self.n = 2**self.h
        self.func = func
        self.op = op
        self.merge = merge
        self.ti = ti
        self.ei = ei
        self.val = [ti for _ in range(2 * self.n)]
        for i in range(len(arr)):
            self.val[self.n + i] = arr[i]
        for i in range(1, self.n)[::-1]:
            self.val[i] = self.func(self.val[2 * i], self.val[2 * i + 1])
        self.laz = [ei for _ in range(2 * self.n)]

    def reflect(self, k):
        if self.laz[k] == self.ei:
            return self.val[k]
        return self.op(self.val[k], self.laz[k])

    def propagate(self, k):
        if self.laz[k] == self.ei: return
        self.laz[2 * k] = self.merge(self.laz[2 * k], self.laz[k])
        self.laz[2 * k + 1] = self.merge(self.laz[2 * k + 1], self.laz[k])
        self.val[k] = self.reflect(k)
        self.laz[k] = self.ei

    def thrust(self, k):
        for i in range(1, self.h + 1)[::-1]:
            self.propagate(k >> i)

    def recalc(self, k):
        while k:
            k >>= 1
            self.val[k] = self.func(self.reflect(2 * k), self.reflect(2 * k + 1))

    def update(self, lt, rt, x):
        lt += self.n
        rt += self.n
        vl = lt
        vr = rt
        self.thrust(lt)
        self.thrust(rt - 1)
        while rt - lt > 0:
            if lt & 1:
                self.laz[lt] = self.merge(self.laz[lt], x)
                lt += 1
            if rt & 1:
                rt -= 1
                self.laz[rt] = self.merge(self.laz[rt], x)
            lt >>= 1
            rt >>= 1
        self.recalc(vl)
        self.recalc(vr - 1)

    def query(self, lt, rt):
        lt += self.n
        rt += self.n
        self.thrust(lt)
        self.thrust(rt - 1)
        vl = vr = self.ti
        while rt - lt > 0:
            if lt & 1:
                vl = self.func(vl, self.reflect(lt))
                lt += 1
            if rt & 1:
                rt -= 1
                vr = self.func(self.reflect(rt), vr)
            lt >>= 1
            rt >>= 1
        return self.func(vl, vr)

def fibonacci(n, mod=1000000007):
    res = [0 for _ in range(n + 1)]
    res[0] = 0
    res[1] = 1
    for i in range(2, n + 1):
        res[i] = res[i - 1] + res[i - 2]
        res[i] %= mod
    return res

import sys
input = sys.stdin.readline

MOD = 1000000007

N, Q = map(int, input().split())

F = fibonacci(N)

arr = [(0, 1, F[i]) for i in range(N)]
ti = (0, 0, 0)
ei = (1, 0, 0)

def func(a, b):
    a1, a2, a3 = a
    b1, b2, b3 = b
    c1 = (a1 + b1) % MOD
    c2 = (a2 + b2) % MOD
    c3 = (a3 + b3) % MOD
    return c1, c2, c3

def op(a, x):
    a1, a2, a3 = a
    x1, x2, x3 = x
    c1 = (a1 * x1 + a2 * x2 + a3 * x3) % MOD
    c2 = a2 % MOD
    c3 = a3 % MOD
    return c1, c2, c3

def merge(x, y):
    x1, x2, x3 = x
    y1, y2, y3 = y
    z1 = (x1 * y1) % MOD
    z2 = (x2 * y1 + y2) % MOD
    z3 = (x3 * y1 + y3) % MOD
    return z1, z2, z3

st = SegmentTreeLazy(arr, ti, ei, func, op, merge)

res = []

for _ in range(Q):
    q, l, r, k = map(int, input().split())
    if q == 0:
        res.append(k * st.query(l, r + 1)[0] % MOD)
    elif q == 1:
        st.update(l, r + 1, (0, k, 0))
    elif q == 2:
        st.update(l, r + 1, (1, k, 0))
    elif q == 3:
        st.update(l, r + 1, (k, 0, 0))
    else:
        st.update(l, r + 1, (1, 0, k))

print('\n'.join(map(str, res)))
0