クエリ3が来たとき、「そのマスが最後にクエリ2で上書きされた時の $x$ に、それより後にクエリ1で加算された値を全て加えた値」を出さないといけない。
あるマスに対するクエリの履歴例（q1:加算、q2:上書き更新）
q1(1) q1(3) q2(5) q1(7) q2(9) q1(2) q1(4) q3 この時の値は?
~~~~~~~~~~~~~~~~~ →ここの合計
クエリ1は、まぁ範囲加算と1点取得なので、Fenwick木なんかで管理することになるだろう。
ただ、「$j$ 列目に対する加算のうち、あるタイミングより後の加算のみを取り出す」ことを、クエリ3の時点でやろうとすると難しい。
クエリ2で上書きされた時に、その時点の列の累積加算値を記録しておけば、クエリ3が来た時点の累積加算値との差分で、クエリ1による加算値は求められる。
q1(1) q1(3) q2(5) q1(7) q2(9) q1(2) q1(4) q3
累積加算値 1 4 11 13 17
＊ この時に現在の値 11 を記録
＊ この時の現在の値 17 との差分 6 が、
最後のクエリ2以降に加算された値
だが、クエリ2が来るたびに全ての列に対して現在値を記録しておく訳にもいかないので、本当に必要な列、
つまり「そのクエリ2で上書きされた値 $x$ を使うようなクエリ3の列」を先読みして、そこのみ記録しておく、といった処理をする必要がある。
まぁ実際にその通りやってもいいんだけど、クエリを逆順に考えると、多少は見通しが良くなる。
クエリ1は、Fenwick木やセグ木などで、各列ごとの累積加算値を管理する
クエリ3が来たら、$(i,j)$ にコマを置き、コマにその時点の $j$ 列目の累積加算値をメモっておく
クエリ2が来たら、その行に置かれている全てのコマについて、以下を行う
クエリ3で記録して、クエリ2で確定、となるので、どの列に対して記録しなければならないかがクエリ順的にわかりやすくなる。
Python3
from operator import add
class FenwickTreeInjectable:
def __init__(self, n, identity_factory, func):
self.size = n
self.tree = [identity_factory() for _ in range(n + 1)]
self.func = func
self.idf = identity_factory
self.depth = n.bit_length()
def add(self, i, x):
i += 1
tree = self.tree
func = self.func
while i <= self.size:
tree[i] = func(tree[i], x)
i += i & -i
def sum(self, i):
i += 1
s = self.idf()
tree = self.tree
func = self.func
while i > 0:
s = func(s, tree[i])
i -= i & -i
return s
def lower_bound(self, x, lt):
"""
累積和がx以上になる最小のindexと、その直前までの累積和
:param lt: lt(a, b) で a < b ならTrueを返す関数
"""
total = self.idf()
pos = 0
tree = self.tree
func = self.func
for i in range(self.depth, -1, -1):
k = pos + (1 << i)
if k > self.size:
continue
new_total = func(total, tree[k])
if lt(new_total, x):
total = new_total
pos += 1 << i
return pos + 1, total
def debug_print(self):
prev = 0
arr = []
for i in range(self.size):
curr = self.sum(i)
arr.append(curr - prev)
prev = curr
print(arr)
n, m, q = map(int, input().split())
queries = []
query3_count = 0
for _ in range(q):
query = list(map(int, input().split()))
if query[0] == 1:
query[1] -= 1
elif query[0] == 2:
query[1] -= 1
else:
query[1] -= 1
query[2] -= 1
query.append(query3_count)
query3_count += 1
queries.append(query)
rows_last_overwritten = [0] * n
rows_q3 = [set() for _ in range(n)]
cols = FenwickTreeInjectable(m + 1, int, add)
ans = [0] * query3_count
for query in reversed(queries):
if query[0] == 1:
l, r, x = query[1:]
cols.add(l, x)
cols.add(r, -x)
elif query[0] == 2:
i, x = query[1:]
for j, qi in rows_q3[i]:
ans[qi] += cols.sum(j) + x
rows_q3[i].clear()
else:
i, j, qi = query[1:]
rows_q3[i].add((j, qi))
ans[qi] -= cols.sum(j)
for i in range(n):
for j, qi in rows_q3[i]:
ans[qi] += cols.sum(j)
print('\n'.join(map(str, ans)))