Submission #48412487

---

Source Code Expand

import os
import sys
from typing import List, Optional, Tuple

sys.setrecursionlimit(210000)
MOD = 998244353

if os.getenv('TEST'):
    def eprint(*args, **kwargs):
        print('[\033[31mEPRINT\033[0m]', *args, file=sys.stderr, **kwargs)
else:
    def eprint(*args, **kwargs):
        pass


def inv(x, m):
    y, u, v = m, 1, 0

    while y != 0:
        t = x // y
        x -= t * y
        u -= t * v
        x, y = y, x
        u, v = v, u

    return u % m


class SegNode(object):
    @staticmethod
    def make_tree(nodes: List['SegNode']) -> 'SegNode':
        parents = nodes[:]
        while len(parents) > 1:
            new_parents = []
            for i in range(0, len(parents), 2):
                if i + 1 < len(parents):
                    new_parents.append(SegNode.make_parent(parents[i], parents[i + 1]))
                else:
                    new_parents.append(parents[i])
            parents = new_parents
        return parents[0]

    @staticmethod
    def make_parent(left_node: 'SegNode', right_node: 'SegNode') -> 'SegNode':
        new_node = SegNode(left_node.left_index, right_node.right_index)
        new_node.left_node = left_node
        new_node.right_node = right_node
        left_node.parent_node = new_node
        right_node.parent_node = new_node
        return new_node

    def __init__(self, left_index: int, right_index: int) -> None:
        self.left_index = left_index
        self.right_index = right_index
        self.left_node: Optional['SegNode'] = None
        self.right_node: Optional['SegNode'] = None
        self.parent_node: Optional['SegNode'] = None
        self.multi_value = 1
        self.add_value = 0

    def update(self, left_index: int, right_index: int, multi_value: int, add_value: int) -> None:
        if self.right_index <= left_index or right_index <= self.left_index:
            return

        if left_index <= self.left_index and self.right_index <= right_index:
            self.apply(multi_value, add_value)
            return

        if self.left_node is not None and self.right_node is not None:
            self.left_node.update(
                self.left_index,
                self.right_index,
                self.multi_value,
                self.add_value)
            self.left_node.update(left_index, right_index, multi_value, add_value)
            self.right_node.update(
                self.left_index,
                self.right_index,
                self.multi_value,
                self.add_value)
            self.right_node.update(left_index, right_index, multi_value, add_value)
            self.multi_value = 1
            self.add_value = 0

    def apply(self, multi_value: int, add_value: int) -> None:
        self.multi_value = (self.multi_value * multi_value) % MOD
        self.add_value = (self.add_value * multi_value + add_value) % MOD

    def get_value(self) -> Tuple[int, int]:
        multi_value = self.multi_value
        add_value = self.add_value
        node = self.parent_node
        while node is not None:
            multi_value = (multi_value * node.multi_value) % MOD
            add_value = (add_value * node.multi_value + node.add_value) % MOD
            node = node.parent_node
        return multi_value, add_value

    def __str__(self) -> str:
        return f'[{self.left_index},{self.right_index}): {self.multi_value}*x+{self.add_value}'


def eprint_tree(root: SegNode) -> None:
    nodes = [root]
    while len(nodes) != 0:
        new_nodes = []
        for node in nodes:
            eprint(node, end='')
            if node.left_node is not None:
                new_nodes.append(node.left_node)
            if node.right_node is not None:
                new_nodes.append(node.right_node)
        eprint()
        nodes = new_nodes


def main() -> None:
    _, M = map(int, input().split())
    A = list(map(int, input().split()))
    nodes = [SegNode(i, i + 1) for i in range(len(A))]
    root = SegNode.make_tree(nodes)

    for _ in range(M):
        L, R, X = map(int, input().split())
        L -= 1
        length = R - L
        multi_value = ((length - 1) * inv(length, MOD)) % MOD
        add_value = (X * inv(length, MOD)) % MOD
        root.update(L, R, multi_value, add_value)

    results: List[int] = []
    for node, a in zip(nodes, A):
        multi_value, add_value = node.get_value()
        results.append((a * multi_value + add_value) % MOD)

    print(*results)


if __name__ == '__main__':
    main()

Submission Info

Judge Result