結果

問題 No.510 二次漸化式
ユーザー gew1fw
提出日時 2025-06-12 13:16:16
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,384 bytes
コンパイル時間 326 ms
コンパイル使用メモリ 82,596 KB
実行使用メモリ 93,188 KB
最終ジャッジ日時 2025-06-12 13:18:55
合計ジャッジ時間 11,971 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other WA * 4 TLE * 1 -- * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

class AffineNode:
    __slots__ = ['a', 'c']
    def __init__(self, a=1, c=0):
        self.a = a
        self.c = c

    def combine(self, other):
        new_a = (self.a * other.a) % MOD
        new_c = (self.a * other.c + self.c) % MOD
        return AffineNode(new_a, new_c)

class SegmentTree:
    def __init__(self, size):
        self.n = size
        self.size = 1
        while self.size < self.n:
            self.size <<= 1
        self.tree = [AffineNode() for _ in range(2 * self.size)]

    def update(self, pos, a, c):
        pos += self.size
        self.tree[pos] = AffineNode(a, c)
        pos >>= 1
        while pos >= 1:
            left = 2 * pos
            right = 2 * pos + 1
            self.tree[pos] = self.tree[left].combine(self.tree[right])
            pos >>= 1

    def query_range(self, l, r):
        res = AffineNode()
        l += self.size
        r += self.size
        while l < r:
            if l % 2 == 1:
                res = res.combine(self.tree[l])
                l += 1
            if r % 2 == 1:
                r -= 1
                res = res.combine(self.tree[r])
            l >>= 1
            r >>= 1
        return res

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

    x = [0] * n
    y = [0] * n

    st = SegmentTree(n)

    for _ in range(q):
        query = input[ptr]
        ptr +=1
        if query == 'x' or query == 'y':
            typ = query
            i = int(input[ptr])
            ptr +=1
            v = int(input[ptr])
            ptr +=1
            if typ == 'x':
                x[i] = v % MOD
            else:
                y[i] = v % MOD
                a = y[i]
                c = 1
                st.update(i, a, c)
        else:
            i = int(input[ptr])
            ptr +=1
            sum_a = 0
            for j in range(i):
                if j ==0:
                    bj = 1
                else:
                    affine = st.query_range(0, j)
                    a = affine.a
                    c_val = affine.c
                    bj = (a * 1 + c_val) % MOD
                term = (x[j] * (bj * bj) % MOD) % MOD
                sum_a = (sum_a + term) % MOD
            a_i = (1 + sum_a) % MOD
            print(a_i)

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