この問題は クエリ平方分割 でも解くことができます。
まずクエリを \(\sqrt Q\) 個の区画に分割し、各区画において「タイプ \(1\) によって \(j\) 列目に足された数の総和」 を前計算しておきましょう。これは imos 法で \(O(Q + M\sqrt Q)\) で出来ます。
次にタイプ \(3\) を順番に処理していきます。
この時、「\(i\) 行目に最後にタイプ \(2\) が適用されたのは0-indexedで何番目のクエリか(なければ \(-1\))」を示す数列 \(Last_i\) を用意し、更新しながら処理します。
タイプ \(3\) の \(Query_k\) に対する答えを \(ans\) とします。 次の手順で \(ans\) が求まります。
0. \(ans = 0\) とおく。
1. \(Last_i \neq -1\) であれば \(ans\) に \(X_{Last_i}\) を加算する。
2. \(Query_{Last_i}\) から \(Query_k\) にかけてタイプ \(1\) を処理し、その総和を \(ans\) に加算する。これは、前計算を部分的に利用すれば\(O(\sqrt Q)\) で出来る。

したがって、この問題を \(O((Q+ M\sqrt Q)+Q \sqrt Q) = O((Q+M)\sqrt Q)\) で解くことができました。
実装例(C++)