結果
| 問題 | No.789 範囲の合計 |
| コンテスト | |
| ユーザー |
 回転
|
| 提出日時 | 2026-08-26 22:49:15 |
| 言語 | Python3 (3.14.7 + numpy 2.5.2 + scipy 1.18.0 + ACL) |
| 結果 |
TLE
不安定
|
| 実行時間 | - |
| コード長 | 8,271 bytes |
| 記録 | |
| コンパイル時間 | 304 ms |
| コンパイル使用メモリ | 21,412 KB |
| 実行使用メモリ | 87,032 KB |
| 最終ジャッジ日時 | 2026-08-26 22:49:35 |
| 合計ジャッジ時間 | 7,518 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 4 TLE * 11 |
ソースコード
class DynamicSegTree:
def __init__(self, n, op, e):
self.n = n
self.op = op
self.e = e
# index 0 は番兵 (存在しない部分木 = 単位元)
self.lc = [0]
self.rc = [0]
self.dat = [e]
self.root = 0
def _new(self):
self.lc.append(0)
self.rc.append(0)
self.dat.append(self.e)
return len(self.dat) - 1
# ------------------------------------------------------------------
# 一点更新・取得
# ------------------------------------------------------------------
def set(self, p: int, x):
"""a[p] = x"""
if p < 0 or p >= self.n:
raise IndexError('DynamicSegTree: index out of range')
if self.root == 0:
self.root = self._new()
t = self.root
a = 0
b = self.n
stack: list[int] = []
while b - a > 1:
stack.append(t)
m = a + ((b - a) >> 1)
if p < m:
nxt = self.lc[t]
if nxt == 0:
nxt = self._new()
self.lc[t] = nxt
t = nxt
b = m
else:
nxt = self.rc[t]
if nxt == 0:
nxt = self._new()
self.rc[t] = nxt
t = nxt
a = m
self.dat[t] = x
while len(stack) > 0:
u = stack.pop()
self.dat[u] = self.op(self.dat[self.lc[u]], self.dat[self.rc[u]])
def apply_at(self, p: int, x):
"""a[p] = op(a[p], x)。未作成の点は e 扱い。1 回の降下で処理。"""
if p < 0 or p >= self.n:
raise IndexError('DynamicSegTree: index out of range')
if self.root == 0:
self.root = self._new()
t = self.root
a = 0
b = self.n
stack: list[int] = []
while b - a > 1:
stack.append(t)
m = a + ((b - a) >> 1)
if p < m:
nxt = self.lc[t]
if nxt == 0:
nxt = self._new()
self.lc[t] = nxt
t = nxt
b = m
else:
nxt = self.rc[t]
if nxt == 0:
nxt = self._new()
self.rc[t] = nxt
t = nxt
a = m
self.dat[t] = self.op(self.dat[t], x)
while len(stack) > 0:
u = stack.pop()
self.dat[u] = self.op(self.dat[self.lc[u]], self.dat[self.rc[u]])
def get(self, p: int):
"""a[p] を返す (未作成なら e)。"""
if p < 0 or p >= self.n:
raise IndexError('DynamicSegTree: index out of range')
t = self.root
a = 0
b = self.n
while t != 0 and b - a > 1:
m = a + ((b - a) >> 1)
if p < m:
t = self.lc[t]
b = m
else:
t = self.rc[t]
a = m
return self.dat[t] # dat[0] == e なので未作成でも正しい
def __getitem__(self, p: int):
return self.get(p)
def __setitem__(self, p: int, x):
self.set(p, x)
def build(self, v, offset: int = 0):
"""リスト v を区間 [offset, offset+len(v)) に一括代入。O(|v| log n)。"""
for i in range(len(v)):
self.set(offset + i, v[i])
# ------------------------------------------------------------------
# 区間積 (非可換モノイド対応・完全非再帰)
# ------------------------------------------------------------------
def prod(self, l: int, r: int):
"""op(a[l], a[l+1], ..., a[r-1]) を返す。l >= r なら e。"""
if l < 0:
l = 0
if r > self.n:
r = self.n
if l >= r:
return self.e
# Phase 0: クエリが片側に収まる間は降下
t = self.root
a = 0
b = self.n
while t != 0:
if l <= a and b <= r:
return self.dat[t]
m = a + ((b - a) >> 1)
if r <= m:
t = self.lc[t]
b = m
elif m <= l:
t = self.rc[t]
a = m
else:
break
if t == 0:
return self.e
m = a + ((b - a) >> 1)
# 左境界の降下: [l, m) を右から左へ畳み込む (resl = op(新区間, resl))
resl = self.e
u = self.lc[t]
x = a
y = m
while u != 0:
if l <= x:
resl = self.op(self.dat[u], resl)
break
mm = x + ((y - x) >> 1)
if l < mm:
rr = self.rc[u]
if rr != 0:
resl = self.op(self.dat[rr], resl)
u = self.lc[u]
y = mm
else:
u = self.rc[u]
x = mm
# 右境界の降下: [m, r) を左から右へ畳み込む (resr = op(resr, 新区間))
resr = self.e
u = self.rc[t]
x = m
y = b
while u != 0:
if y <= r:
resr = self.op(resr, self.dat[u])
break
mm = x + ((y - x) >> 1)
if r > mm:
ll = self.lc[u]
if ll != 0:
resr = self.op(resr, self.dat[ll])
u = self.rc[u]
x = mm
else:
u = self.lc[u]
y = mm
return self.op(resl, resr)
def all_prod(self):
return self.dat[self.root]
# ------------------------------------------------------------------
# 木上二分探索 (ACL 互換。再帰だが深さは高々 log2(n) <= 63)
# ------------------------------------------------------------------
def max_right(self, l: int, g):
"""g(op(a[l..r))) が true となる最大の r を返す。
条件: g(e) == true, 0 <= l <= n。g は単調 (true→…→false) を仮定。"""
pos, _ = self._mr(self.root, 0, self.n, l, g, self.e)
return self.n if pos < 0 else pos
def _mr(self, t: int, a: int, b: int, l: int, g, sm):
if b <= l or t == 0:
return (-1, sm) # 空 or 全て e → sm 不変・境界なし
if l <= a:
tot = self.op(sm, self.dat[t])
if g(tot):
return (-1, tot) # 区間全体 OK → 境界はさらに右
if b - a == 1:
return (a, sm) # 境界確定
m = a + ((b - a) >> 1)
pos, sm = self._mr(self.lc[t], a, m, l, g, sm)
if pos >= 0:
return (pos, sm)
return self._mr(self.rc[t], m, b, l, g, sm)
def min_left(self, r: int, g):
"""g(op(a[l..r))) が true となる最小の l を返す。
条件: g(e) == true, 0 <= r <= n。"""
pos, _ = self._ml(self.root, 0, self.n, r, g, self.e)
return 0 if pos < 0 else pos
def _ml(self, t: int, a: int, b: int, r: int, g, sm):
if a >= r or t == 0:
return (-1, sm)
if b <= r:
tot = self.op(self.dat[t], sm)
if g(tot):
return (-1, tot)
if b - a == 1:
return (b, sm)
m = a + ((b - a) >> 1)
pos, sm = self._ml(self.rc[t], m, b, r, g, sm)
if pos >= 0:
return (pos, sm)
return self._ml(self.lc[t], a, m, r, g, sm)
# ------------------------------------------------------------------
# その他
# ------------------------------------------------------------------
def node_count(self) -> int:
"""生成済みノード数 (メモリ使用量の目安)。"""
return len(self.dat) - 1
def clear(self):
self.lc = [0]
self.rc = [0]
self.dat = [self.e]
self.root = 0
N = int(input())
T = DynamicSegTree(10**9+100, int.__add__, 0)
ans = 0
for _ in range(N):
query = list(map(int,input().split()))
if(query[0] == 0):
_,x,y = query
T.set(x, T.get(x) + y)
else:
_,l,r = query
ans += T.prod(l,r+1)
print(ans)