問題 長さNの整数列a_iが与えられます $Q$個のクエリを処理してください given l, r, x: $a_l \cdots a_r$を$x$倍 given l, r: $a_l \times a_{l+1} \times \cdots \times a_r \bmod 998244353$を出力 $O(\log N)$ per queryで解けるがおそらく$O( \log^{2} N)$と識別不可能。 ちなみに元ネタはこれ(解法は違う): 区間代入/区間積 Θ(logN)/query - noshi91のメモ $O(\log^{2} N)$ 解法 普通に遅延伝搬segtreeに乗せる。…