ありがちな解法で考えると、セグメント木に $(A_i,B_i)$ なんかを乗せ、
集約値の区間最大値を取得！としたいところだが、
それまでの $v$ の値によって最適な選択が異なってくる。
「1を乗算」は意味が無いので、$B_i=1$ の時には必ず「$A_i$ を加算」を選んでよい。
そのような $i$ が連続していれば、$A_i$ の区間和としてセグメント木でまとめて求められる。
なんか、感覚的に “クエリ” は “問い合わせ”、つまり「答えを知らないので教えて」という質問であることを想像するので、
こういう風な「実は問う側が答えを分かってることを前提とした解法」は、ちょっと発想の外から殴られたような衝撃を感じる。
まぁ、「計算途中で $10^{18}$ を超えたら“overflow”を出力して」という仕様だったら別に問う側が知ってなくても成り立つし、
そこから競技プログラミングの問題上、煩雑な部分を省略しただけとも捉えられるので、勝手な感覚ではあるんだけど。
from operator import le, add
class SegmentTreeInjectable:
"""
単位元生成関数 identity_factory と二項演算関数 func を外部注入するセグメント木
[生成]
SegmentTreeInjectable(n, identity_factory, func)
SegmentTreeInjectable.from_array(array, identity_factory, func) # 既存の配列より作成
[関数]
add(i, x) Aiにxを加算
update(i, x) Aiをxに書き換え
get_range(a, b) [a, b) の集約値を得る
get_all() 全ての集約値を得る
get_point(i) Aiを得る
leftmost(a, b, x, ev) [a, b) の範囲で、ev(x, Ai)=True となる最も左の i を得る（前提条件あり）
rightmost(a, b, x, ev) [a, b) の範囲で、ev(x, Ai)=True となる最も右の i を得る（前提条件あり）
debug_print() 深さ毎に整形して出力する
"""
def __init__(self, n, identity_factory, func):
n2 = 1 << (n - 1).bit_length()
self.offset = n2
self.tree = [identity_factory() for _ in range(n2 << 1)]
self.func = func
self.idf = identity_factory
@classmethod
def from_array(cls, arr, identity_factory, func):
""" 既存の配列から生成 """
ins = cls(len(arr), identity_factory, func)
ins.tree[ins.offset:ins.offset + len(arr)] = arr
for i in range(ins.offset - 1, 0, -1):
l = i << 1
r = l + 1
ins.tree[i] = func(ins.tree[l], ins.tree[r])
return ins
def add(self, i, x):
"""
Aiにxを加算
:param i: index (0-indexed)
:param x: add value
"""
i += self.offset
self.tree[i] = self.func(self.tree[i], x)
self.__upstream(i)
def update(self, i, x):
"""
Aiの値をxに更新
:param i: index(0-indexed)
:param x: update value
"""
i += self.offset
self.tree[i] = x
self.__upstream(i)
def __upstream(self, i):
tree = self.tree
func = self.func
while i > 1:
i >>= 1
lch = i << 1
rch = lch | 1
tree[i] = func(tree[lch], tree[rch])
def get_range(self, a, b):
"""
[a, b)の値を得る
:param a: index(0-indexed)
:param b: index(0-indexed)
"""
tree = self.tree
func = self.func
result_l = self.idf()
result_r = self.idf()
l = a + self.offset
r = b + self.offset
while l < r:
if r & 1:
result_r = func(tree[r - 1], result_r)
if l & 1:
result_l = func(result_l, tree[l])
l += 1
l >>= 1
r >>= 1
return func(result_l, result_r)
def get_all(self):
return self.tree[1]
def get_point(self, i):
return self.tree[i + self.offset]
def leftmost(self, a, b, x, ev):
"""
[a, b) の範囲で、ev(x, 値) = True となる最初の index を得る。存在しない場合は-1。
使用できる条件:
[l, r) の集約値を y としたとき、ev(x, y)=True となることが、
l <= i < r 内に ev(x, Ai)=True となる要素があることと等しい。（(func, ev) = (min,ge), (max,le) など）
"""
tree = self.tree
l = a + self.offset
r = b + self.offset
r_found = -1
while l < r:
if l & 1:
if ev(x, tree[l]):
return self._leftmost_sub(l, x, ev)
l += 1
if r & 1:
if ev(x, tree[r - 1]):
r_found = r - 1
l >>= 1
r >>= 1
if r_found == -1:
return -1
return self._leftmost_sub(r_found, x, ev)
def _leftmost_sub(self, i, x, ev):
"""
tree-index i が示す範囲で、ev(x, Aj)=True となる最も左のarray-index j を得る
（tree[i] が示す範囲には条件を満たすものが必ず存在する前提とする）
"""
tree = self.tree
while i < self.offset:
l = i << 1
if ev(x, tree[l]):
i = l
else:
i = l + 1
return i - self.offset
def rightmost(self, a, b, x, ev):
"""
[a, b) の範囲で、ev(x, 値) = True となる最後の index を得る。存在しない場合は-1。
使用できる条件:
[l, r) の集約値を y としたとき、ev(x, y)=True となることが、
l <= i < r 内に ev(x, Ai)=True となる要素があることと等しい。（(func, ev) = (min,ge), (max,le) など）
"""
tree = self.tree
l = a + self.offset
r = b + self.offset
l_found = -1
while l < r:
if r & 1:
if ev(x, tree[r - 1]):
return self._rightmost_sub(r - 1, x, ev)
if l & 1:
if ev(x, tree[l]):
l_found = l
l += 1
l >>= 1
r >>= 1
if l_found == -1:
return -1
return self._rightmost_sub(l_found, x, ev)
def _rightmost_sub(self, i, x, ev):
"""
tree-index i が示す範囲で、ev(x, Aj)=True となる最も右のarray-index j を得る
（tree[i] が示す範囲には条件を満たすものが必ず存在する前提とする）
"""
tree = self.tree
while i < self.offset:
l = i << 1
if ev(x, tree[l + 1]):
i = l + 1
else:
i = l
return i - self.offset
def debug_print(self):
i = 1
while i <= self.offset:
print(self.tree[i:i * 2])
i <<= 1
n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
sgt_a = SegmentTreeInjectable.from_array(aaa, int, add)
sgt_b = SegmentTreeInjectable.from_array(bbb, int, max)
q = int(input())
buf = []
for _ in range(q):
op, i, x = map(int, input().split())
if op == 1:
i -= 1
sgt_a.update(i, x)
elif op == 2:
i -= 1
sgt_b.update(i, x)
else:
v = 0
i -= 1
l, r = i, x
while l < r:
m = sgt_b.leftmost(l, r, 2, le)
if m == -1:
v += sgt_a.get_range(l, r)
break
if l < m:
v += sgt_a.get_range(l, m)
a = sgt_a.get_point(m)
b = sgt_b.get_point(m)
v = max(v + a, v * b)
l = m + 1
buf.append(v)
print('\n'.join(map(str, buf)))