結果

問題 No.8121 [Deleted]
コンテスト
ユーザー nasutarou1341
提出日時 2025-04-01 21:57:08
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,625 bytes
コンパイル時間 426 ms
コンパイル使用メモリ 82,576 KB
実行使用メモリ 119,484 KB
最終ジャッジ日時 2025-04-01 21:57:16
合計ジャッジ時間 7,647 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

class segtree:
  #セグメント木
  def __init__(s, v, op, e):
    s._n = len(v)
    s.log = s.ceil_pow2(s._n)
    s.size = 1 << s.log
    s.d = [e()] * (2 * s.size)
    s.e = e
    s.op = op
    for i in range(s._n): s.d[s.size + i] = v[i]
    for i in range(s.size - 1, 0, -1): s.update(i)
  
  # 1点更新
  def set(s, p, x):
    p += s.size
    s.d[p] = x
    for i in range(1, s.log + 1): s.update(p >> i)
 
  # 1点取得
  def get(s, p):
    return s.d[p + s.size]
 
  # 区間演算
  def prod(s, l, r):
    sml, smr = s.e(), s.e()
    l += s.size
    r += s.size
    while (l < r):
      if l & 1: 
        sml = s.op(sml, s.d[l])
        l += 1
      if r & 1:
        r -= 1
        smr = s.op(s.d[r], smr)
      l >>= 1
      r >>= 1
    return s.op(sml, smr)
 
  # 全体演算
  def all_prod(s): return s.d[1]
 
  # L固定時の最長区間のR
  def max_right(s, l, g):
    if l == s._n: return s._n
    l += s.size
    sm = s.e()
    while True:
      while (l % 2 == 0): l >>= 1
      if not g(s.op(sm, s.d[l])):
        while l < s.size:
          l = 2 * l
          if g(s.op(sm, s.d[l])):
            sm = s.op(sm, s.d[l])
            l += 1
        return l - s.size
      sm = s.op(sm, s.d[l])
      l += 1
      if (l & -l) == l: break
    return s._n
 
  # R固定時の最長区間のL
  def min_left(s, r, g):
    if r == 0: return 0
    r += s.size
    sm = s.e()
    while True:
      r -= 1
      while r > 1 and (r % 2): r >>= 1
      if not g(s.op(s.d[r], sm)):
        while r < s.size:
          r = 2 * r + 1
          if g(s.op(s.d[r], sm)):
            sm = s.op(s.d[r], sm)
            r -= 1
        return r + 1 - s.size
      sm = s.op(s.d[r], sm)
      if (r & - r) == r: break
    return 0
 
  def update(s, k): s.d[k] = s.op(s.d[2 * k], s.d[2 * k + 1])
  def ceil_pow2(s, n):
    x = 0
    while (1 << x) < n: x += 1
    return x
  def print(s): #デバッグ用
    ans = []
    for i in range(s._n):
      ans.append(s.get(i))
    print(*ans)
  
class segtreeFactory:
  MAX_INT = 10 ** 18
  MOD = 998244353
  # サイズNのmaxSegTree
  @staticmethod
  def makeMaxSegTree(N,  v = None):
    if v == None: v = [0] * N
    return segtree(v, segtreeFactory.opmax, segtreeFactory.emax)
  # サイズNのminSegTree
  @staticmethod
  def makeMinSegTree(N, v = None):
    if v == None: v = [segtreeFactory.MAX_INT] * N
    return segtree(v, segtreeFactory.opmin, segtreeFactory.emin)
  # サイズNのsumSegTree
  @staticmethod
  def makeSumSegTree(N, v = None):
    if v == None: v = [0] * N
    return segtree(v, segtreeFactory.opsum, segtreeFactory.emax)
  # サイズNのfuncSegTree (一次関数の結合)
  @staticmethod
  def makeFuncSegTree(N, v = None):
    if v == None: v = [[1, 0] for _ in range(N)]
    return segtree(v, segtreeFactory.opfunc, segtreeFactory.efunc)
  @staticmethod
  def emax(): return 0
  @staticmethod
  def opmax(s, t): return max(s, t)
  @staticmethod
  def emin(): return segtreeFactory.MAX_INT
  @staticmethod
  def opmin(s, t): return min(s, t)
  @staticmethod
  def opsum(s, t): return s + t
  @staticmethod
  def efunc(): return [1, 0]
  @staticmethod
  def opfunc(s, t): return [s[0] * t[0] % segtreeFactory.MOD, (t[0] * s[1] + t[1]) % segtreeFactory.MOD] # 左を内側にして結合

N, Q = list(map(int, input().split()))
A = list(map(int, input().split()))
Query = [list(map(int, input().split())) for _ in range(Q)]

seg = segtreeFactory.makeMaxSegTree(N, A)
for q, a, b in Query:
  if q == 1:
    a -= 1
    seg.set(a, (seg.get(a) + b))
  elif q == 2:
    a -= 1
    if b >= N + 1: 1 / 0
    ans = seg.prod(a, b)
    print(ans)
0