操作を逆順に見ることにすると、各操作は「左上のマスを\((1,1)\)、右下のマスを\((R_i,C_i)\)とする長方形に含まれるマスのうち、まだ一度も上書きされていないマスを英大文字\(X_i\)で上書きする」という操作になります。

ここで、操作の制約より、あるマス\((x,y)\)が上書きされているとき、\(a\leq x,b\leq y\)を満たすマス\((a,b)\)もすべて上書きされていることになります。

よって、上書きを以下の疑似コードのように愚直に行うことにすると、（いったん時間計算量を無視すれば）正しく答えが求まることがわかります。

// P[x][y] : マス(x,y)が何回目の操作で上書きされたか（まだ上書きされていないなら0）
for (int i = Q; i >= 1; i--) {
    for (int x = R[i]; x >= 1; x--) {
        if (P[x][C[i]] != 0) break;
        for (int y = C[i]; y >= 1; y--) {
            if (P[x][y] != 0) break;
            P[x][y] = i;
        }
    }
}

次に、この疑似コードの各処理が実行される回数について考えると、以下のようになります。

• 4行目：各\(i(1\leq i\leq Q)\)について高々1回しか実行されないため、全体で\(\Omicron(Q)\)回
• 6行目：この処理が行われうるのはマス\((x,y+1)\)が上書きされた直後のみであるため、全体で\(\Omicron(HW)\)回
• 7行目：各マスについて高々1回しか実行されないため、全体で\(\Omicron(HW)\)回

したがって、全体での時間計算量が\(\Omicron(HW+Q)\)となっているため、以上の解法でこの問題を解くことができます。