最初、全要素が0なので答えは言うまでも無く0。
たとえば $a$ の1個 $a_i$ を $5$ から $10$ に変えたときに、全体の答えがどうなるか考えると、
これで全て。
なので、差分だけ更新していくことで、クエリに高速に答えられそう。
なお、$10$ から $5$ に変わるなど値が減少するときは、3つめの増加と減少が逆転する。
範囲の個数や総和を求めたいので、セグメント木やFenwick Treeで管理すればよい。
「$a$ 用、$b$ 用」「個数用、総和用」で合計4つ、必要になる。
$Y_i$ の取り得る範囲が $10^8$ と大きいので、座標圧縮の必要がある。
今回は「$a_i$ を $Y_{old}$ から $Y_{new}$ に変えるとき、この間の個数や総和」が求まればよい、つまり $Y_i$ の大小関係さえ保たれていれば範囲指定できるので、
$Y_i$ として出てくる値をソートして小さい順に $0,1,2,...$ に対応させれば、$Q$ の長さ $2 \times 10^5$ として扱うことができる。
範囲の境界（以下なのか未満なのか、など）に注意。
どちらでもよいが、$a_i=b_j$ となる $b_j$ があり、今まで $\max(a_i,b_j)=b_j$ だった場合、それを「$\max(a_i,b_j)=a_i$ に変わったと見なし、更新対象に含めるのか（同じ値が引かれ、足されるので実質は変化ない）」「変化無しとして更新対象に含めないのか」は、3種類の更新の中で統一しておく必要がある。
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
n, m, q = map(int, input().split())
y_appear = set()
queries = []
for _ in range(q):
t, x, y = map(int, input().split())
y_appear.add(y)
queries.append((t - 1, x - 1, y))
compress = {y: i + 1 for i, y in enumerate(sorted(y_appear))}
compress[0] = 0
fwt = [
{
'count': FenwickTreeInjectable(len(compress) + 5, int, add),
'total': FenwickTreeInjectable(len(compress) + 5, int, add),
},
{
'count': FenwickTreeInjectable(len(compress) + 5, int, add),
'total': FenwickTreeInjectable(len(compress) + 5, int, add),
},
]
fwt[0]['count'].add(0, n)
fwt[1]['count'].add(0, m)
current = [[0] * n, [0] * m]
buf = []
ans = 0
for t, x, y in queries:
i = compress[y]
z = current[t][x]
j = compress[z]
get = fwt[t ^ 1]['count'].sum(i) * y
loss1 = fwt[t ^ 1]['count'].sum(j - 1) * z
loss2 = fwt[t ^ 1]['total'].sum(i) - fwt[t ^ 1]['total'].sum(j - 1)
ans += get - loss1 - loss2
fwt[t]['count'].add(i, 1)
fwt[t]['count'].add(j, -1)
fwt[t]['total'].add(i, y)
fwt[t]['total'].add(j, -z)
current[t][x] = y
buf.append(ans)
print('\n'.join(map(str, buf)))