\(X_i\) で上書きするのではなく \(i\) で上書きすると考えてみましょう。これが解ければ、最後に \(i\) を \(X_i\) と書き直すことでこの問題を解くことができます。

さて、操作終了時に \((r, c)\) に書かれる数は「 \(r \le R_i, c \le C_i\) であるような \(i\) のうち、最も大きな \(i\)」であるはずです。これを求めるには、以下のような問題が解ければよいはずです。

• グリッドのいくつかのマスに数字を書き込む。その後、すべてのマスについて「自分の右下の長方形領域に書かれている数のうち、最大の値」を求める

これは、二次元 imos 法を右下から左上に向かって適用していくことで求めることができます。計算量は \(O(HW + Q)\) です。

実装例(PyPy)

h, w, q = map(int, input().split())

a = [[0] * w for i in range(h)]
xs = ["A"]
for i in range(1, q + 1):
    r, c, x = input().split()
    xs.append(x)
    a[int(r)-1][int(c)-1] = i

for r in range(h - 1, -1, -1):
    for c in range(w - 1, -1, -1):
        if r != 0: a[r-1][c] = max(a[r][c], a[r-1][c])
        if c != 0: a[r][c-1] = max(a[r][c], a[r][c-1])

for r in range(h):
    print("".join(xs[a[r][c]] for c in range(w)))