結果

問題 No.749 クエリ全部盛り
ユーザー toyuzukotoyuzuko
提出日時 2020-05-14 21:46:32
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,050 bytes
コンパイル時間 248 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 283,804 KB
最終ジャッジ日時 2024-09-16 00:38:34
合計ジャッジ時間 13,644 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
58,496 KB
testcase_01 AC 44 ms
52,864 KB
testcase_02 AC 43 ms
53,120 KB
testcase_03 AC 44 ms
52,864 KB
testcase_04 AC 46 ms
52,992 KB
testcase_05 AC 333 ms
81,144 KB
testcase_06 AC 325 ms
80,552 KB
testcase_07 AC 343 ms
80,356 KB
testcase_08 AC 341 ms
80,860 KB
testcase_09 AC 351 ms
81,048 KB
testcase_10 AC 1,294 ms
98,100 KB
testcase_11 AC 1,324 ms
96,040 KB
testcase_12 AC 1,240 ms
96,076 KB
testcase_13 AC 1,295 ms
98,204 KB
testcase_14 AC 1,267 ms
96,560 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.buffer.readline

MOD = 1000000007
MODsq = MOD**2

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

F = fibonacci(N)

arr = [MOD + F[i] for i in range(N)]
ti = 0
ei = MODsq

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

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

def merge(x, y):
    x3 = x % MOD
    x2 = (x - x3) // MOD % MOD
    x1 = (x - x3 - x2 * MOD) // MODsq
    y3 = y % MOD
    y2 = (y - y3) // MOD % MOD
    y1 = (y - y3 - y2 * MOD) // MODsq
    z1 = (x1 * y1) % MOD
    z2 = (x2 * y1 + y2) % MOD
    z3 = (x3 * y1 + y3) % MOD
    return z1 * MODsq + z2 * MOD + 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:
        x = st.query(l, r + 1)
        x3 = x % MOD
        x2 = (x - x3) // MOD % MOD
        x1 = (x - x3 - x2 * MOD) // MODsq
        res.append(k * x1 % MOD)
    elif q == 1:
        st.update(l, r + 1, k * MOD)
    elif q == 2:
        st.update(l, r + 1, MODsq + k * MOD)
    elif q == 3:
        st.update(l, r + 1, k * MODsq)
    else:
        st.update(l, r + 1, MODsq + k)

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