Submit Info #54847

Problem Lang User Status Time Memory
Range Affine Range Sum pypy3 atabi AC 3411 ms 140.56 MiB

ケース詳細
Name Status Time Memory
example_00 AC 48 ms 29.81 MiB
max_random_00 AC 3411 ms 140.56 MiB
max_random_01 AC 3204 ms 140.43 MiB
max_random_02 AC 3194 ms 139.80 MiB
random_00 AC 2511 ms 136.98 MiB
random_01 AC 2651 ms 139.47 MiB
random_02 AC 1420 ms 105.03 MiB
small_00 AC 60 ms 29.93 MiB
small_01 AC 66 ms 30.31 MiB
small_02 AC 73 ms 30.44 MiB
small_03 AC 70 ms 30.43 MiB
small_04 AC 90 ms 31.57 MiB
small_05 AC 86 ms 30.94 MiB
small_06 AC 90 ms 30.81 MiB
small_07 AC 85 ms 31.20 MiB
small_08 AC 94 ms 31.57 MiB
small_09 AC 91 ms 31.31 MiB
small_random_00 AC 139 ms 33.18 MiB
small_random_01 AC 127 ms 32.56 MiB

####################################################### # Range Affine Range Sum ####################################################### import sys input = lambda: sys.stdin.readline().rstrip() class LazySegmentTree: # 初期化処理 # op (X, X) -> X : SegmentTreeにのせるモノイド # ieX : opに対する単位元 # mapping : (X, A) -> X # composition : (A, A) -> A def __init__(self, init, op, ie, mapping, composition, _id): self._op = op self._ie = ie if type(init) == int: init = [ie] * init self._n = len(init) self._log = (self._n-1).bit_length() # seg木の深さ self._size = 1 << self._log # seg木のサイズ # seg木の初期化 self._dat = [ie] * self._size + init + [ie] * (self._size - len(init)) for i in range(self._size-1, 0, -1): self._update(i) self._id = _id # 遅延情報の初期値 self._lazy = [_id] * self._size # 遅延情報 self._mapping = mapping self._composition = composition def set(self, i, x): # 一点更新 i += self._size for k in range(self._log, 0, -1): self._push(i >> k) self._dat[i] = x while i > 0: # 層をのぼりながら値を更新 indexが0になれば終了 i >>= 1 # 1つ上の層のインデックス(完全二分木における親) # 下の層2つの演算結果の代入(完全二分木における子同士の演算) self._update(i) def getvalue(self, i): # 一点取得 i += self._size for k in range(self._log, 0, -1): self._push(i >> k) return self._dat[i] def query(self, l, r): # range query if l == r: return self._ie l += self._size # 1番下の層におけるインデックス r += self._size # 1番下の層におけるインデックス indices = self._get_indices(l, r) for index in reversed(indices): self._push(index) lret, rret = self._ie, self._ie # 左側の答えと右側の答えを初期化 while l < r: # lとrが重なるまで上記の判定を用いて演算を実行 # 左が子同士の右側(lが奇数)(lの末桁=1)ならば、dat[l]を加算 if l & 1: lret = self._op(lret, self._dat[l]) l += 1 # 右が子同士の右側(rが奇数)(rの末桁=1)ならば、dat[r-1]を演算 if r & 1: r -= 1 rret = self._op(self._dat[r], rret) # モノイドでは可換律は保証されていないので演算の方向に注意 l >>= 1 r >>= 1 return self._op(lret, rret) def all_prod(self): return self._dat[1] def apply(self, l, r, f): if l == r: return l += self._size # 1番下の層におけるインデックス r += self._size # 1番下の層におけるインデックス indices = self._get_indices(l, r) for i in reversed(indices): self._push(i) while l < r: if l & 1: self._apply(l, f) l += 1 if r & 1: r -= 1 self._apply(r, f) l >>= 1 r >>= 1 for i in indices: self._update(i) def max_right(self, l, isOk): if l >= self._n: return self._n l += self._size for i in range(self._log, 0, -1): self._push(l >> i) sm = self._ie while True: while l % 2 == 0: l >>= 1 if not isOk(self._op(sm, self._dat[l])): while l < self._size: self._push(l) l <<= 1 if isOk(self._op(sm, self._dat[l])): sm = self._op(sm, self._dat[l]) l += 1 return l - self._size sm = self._op(sm, self._dat[l]) l += 1 if l & -l == l: break return self._n def min_left(self, r, isOk): if r <= 0: return 0 r += self._size for i in range(self._log, 0, -1): self._push((r - 1) >> i) sm = self._ie while True: first = False r -= 1 while r > 1 and r % 2: r >>= 1 if not isOk(self._op(self._dat[r], sm)): while r < self._size: self._push(r) r = r << 1 | 1 if isOk(self._op(self._dat[r], sm)): sm = self._op(self._dat[r], sm) r -= 1 return r + 1 - self._size sm = self._op(self._dat[r], sm) if r & -r == r: break return 0 def _update(self, i): # 集約する self._dat[i] = self._op(self._dat[i*2], self._dat[i*2+1]) def _apply(self, i, f): # 遅延情報で計算する self._dat[i] = self._mapping(f, self._dat[i]) # 最下層より上の場合、遅延情報を累積する if i < self._size: self._lazy[i] = self._composition(f, self._lazy[i]) # 遅延情報を下に落とす def _push(self, i): self._apply(i<<1, self._lazy[i]) self._apply(i<<1|1, self._lazy[i]) self._lazy[i] = self._id def _get_indices(self, l, r): """ l, r are already added offset """ result = [] l0 = (l // (l & -l)) >> 1 r0 = (r // (r & -r)) >> 1 while l0 != r0: if l0 > r0: result.append(l0) l0 >>= 1 else: result.append(r0) r0 >>= 1 while l0: result.append(l0) l0 >>= 1 return result ####################################################### # a = (a_0, ..., a_n-1) # 0 l r b c:l <= i < r に対して a_i <- b * a_i + c # 1 l r: sigma(l <= i < r)a_i mod 998244353 ####################################################### # 各要素は 30 bitオフセットさせて持つ # 区間の合計sum(l, r) + 区間の長さ l - r shift = 30 mask = (1 << shift) - 1 # 区間集約演算 *: X * X -> X の定義. def op(x, y): z = x + y ret = (z >> shift) % mod << shift ret |= z & mask return ret # op演算の単位元 e = 0 # 区間更新演算 ·: X · M -> X の定義. # Affine変換 b*a_i + c # f = (b, c) def mapping(f, a): b, c = f sa, la = divmod(a, 1 << shift) ret = b*sa + c*la # Σ(b*a_i + c) = b * Σa_i + c*(r-l) ret = (ret % mod) << shift ret |= la return ret # 遅延評価演算 ·: M · M -> M の定義. # f・g = f(g(x)) def composition(f, g): bf, cf = f bg, cg = g return ((bf*bg)%mod, (bf*cg+cf)%mod) # 遅延評価演算の単位元 # a_i = 1*a_i + 0 id_ = (1, 0) ####################################################### mod = 998244353 n, q = map(int, input().split()) # a_i = a_i + 区間の長さ a = [x << shift | 1 for x in map(int, input().split())] sgt = LazySegmentTree(a, op, e, mapping, composition, id_) for _ in range(q): t, *qry = map(int, input().split()) if t == 0: l, r, b, c = qry sgt.apply(l, r, (b, c)) else: l, r = qry ans = sgt.query(l, r)>>shift print(ans)