すべてのマスに対して、最終的なマスの色はそのマスに対する最後の操作により決まります。このような状況では、操作を逆順から考えることにより扱いやすくなるケースが多いです。

操作を逆順から考えることにより、問題における一連の操作は以下と等価であることがわかります。

\(H\) 行 \(W\) 列のグリッドが与えられ、はじめすべてのマスの色は未確定である。

\(i = M,M-1,\ldots,1\) の順で以下の操作を行う。

• \(T_i = 1\) のとき、\(A_i\) 行目のマスであって、マスの色が未確定であるものの色を \(X_i\) であると確定させる。

• \(T_i = 2\) のとき、\(A_i\) 列目のマスであって、マスの色が未確定であるものの色を \(X_i\) であると確定させる。

以上の操作を終えた後に色が未確定であるマスの色が色 \(0\) であると確定させる。

このように整理すると、 \(i = M,M-1,\ldots, 1\) の順で \(1\) 度以上操作を行った行・列の個数、各行・列に対して操作を行ったかどうか、各色の確定したマスの個数の情報を持ちながら計算することで答えを計算できることがわかります。

具体的には、\(A_i\) 行目に対する操作はそれ以前に \(A_i\) 行目に対する操作が行われていないときに限り行われると考えてよく、その操作においては操作を行われたことのない列の個数だけ色 \(X_i\) であると確定するマスの個数が増え、\(A_i\) 列目に対する操作でも同様です。

実装例

#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); i++)
using namespace std;
using ll = long long;

int main() {
    int h, w, m;
    cin >> h >> w >> m;
    vector<bool> f(h), g(w); // 操作が行われたことがあるか
    ll hc = h, wc = w; // 操作が行われていない行・列の個数
    vector<int> t(m), a(m), x(m);
    rep(i, m) cin >> t[i] >> a[i] >> x[i];
    rep(i, m) a[i]--;
    int X = 200010;
    vector<ll> cnt(X); // 各色の確定したマスの個数
    for (int i = m - 1; i >= 0; i--) {
        if (t[i] == 1) {
            if (!f[a[i]]) {
                hc--;
                f[a[i]] = true;
                cnt[x[i]] += wc;
            }
        }
        else {
            if (!g[a[i]]) {
                wc--;
                g[a[i]] = true;
                cnt[x[i]] += hc;
            }
        }
    }
    cnt[0] += hc * wc;
    vector<pair<ll, ll>> ans;
    rep(i, X) if (cnt[i]) ans.push_back({ i,cnt[i] });
    cout << ans.size() << '\n';
    for (auto p : ans) cout << p.first << ' ' << p.second << '\n';
}