我们考虑动态维护答案。如果已经知道上一步的答案，考虑计算这一次操作之后答案的变化。
考虑现在有一个数列 \(a_{1 \sim n}\)，我们想知道 \(\sum\limits_{i = 1}^n \max(x, a_i)\)。
计算出 \(c = \sum\limits_{i = 1}^n [a_i < x], s = \sum\limits_{i = 1}^n [a_i \ge x] a_i\)，答案显然就是 \(s + c \times x\)。
这题和上面的题本质相同。以第一种操作为例，每次答案减去旧的 \(a_x\) 对 \(b\) 造成的贡献，再加上 \(y\) 对 \(b\) 造成的贡献。第二种操作是对称的。
于是我们只需要对 \(y_i\) 离散化后，行和列分别维护两个树状数组表示 \(\sum\limits_{i = 1}^n [a_i \le x]\) 和 \(\sum\limits_{i = 1}^n [a_i \le x] a_i\)，一共四个树状数组即可。
时间复杂度 \(O(q \log (q + n + m))\)。
code
// Problem: F - Max Matrix
// Contest: AtCoder - Japanese Student Championship 2021
// URL: https://atcoder.jp/contests/jsc2021/tasks/jsc2021_f
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
ll n, m, q, a[maxn], b[maxn], lsh[maxn], tot;
struct node {
ll op, x, y;
} c[maxn];
struct BIT {
ll c[maxn];
inline void update(int x, ll d) {
for (int i = x; i <= tot; i += (i & (-i))) {
c[i] += d;
}
}
inline ll query(int x) {
ll res = 0;
for (int i = x; i; i -= (i & (-i))) {
res += c[i];
}
return res;
}
inline ll query(int l, int r) {
return query(r) - query(l - 1);
}
} t1, t2, t3, t4;
inline ll calc1(ll x) {
return t4.query(x, tot) + lsh[x] * t3.query(x - 1);
}
inline ll calc2(ll x) {
return t2.query(x, tot) + lsh[x] * t1.query(x - 1);
}
void solve() {
scanf("%lld%lld%lld", &n, &m, &q);
lsh[++tot] = 0;
for (int i = 1; i <= q; ++i) {
scanf("%lld%lld%lld", &c[i].op, &c[i].x, &c[i].y);
lsh[++tot] = c[i].y;
}
sort(lsh + 1, lsh + tot + 1);
tot = unique(lsh + 1, lsh + tot + 1) - lsh - 1;
for (int i = 1; i <= n; ++i) {
a[i] = 1;
}
for (int i = 1; i <= m; ++i) {
b[i] = 1;
}
t1.update(1, n);
t3.update(1, m);
ll ans = 0;
for (int i = 1; i <= q; ++i) {
ll op = c[i].op, x = c[i].x, y = c[i].y;
y = lower_bound(lsh + 1, lsh + tot + 1, y) - lsh;
if (op == 1) {
t1.update(a[x], -1);
t2.update(a[x], -lsh[a[x]]);
ans -= calc1(a[x]);
a[x] = y;
t1.update(y, 1);
t2.update(y, lsh[y]);
ans += calc1(y);
} else {
t3.update(b[x], -1);
t4.update(b[x], -lsh[b[x]]);
ans -= calc2(b[x]);
b[x] = y;
t3.update(y, 1);
t4.update(y, lsh[y]);
ans += calc2(y);
}
printf("%lld\n", ans);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}