お宝の種類ごとに2次元累積和をもつことを考えます。クエリ1はナイーブに処理すると \(O(NM)\) かかりますが、隣接するお宝をswapしていることに着目すると累積和が変化する部分は高々1行 or 1列なので \(O(N+M)\) で処理することができます。クエリ2は \(O(K)\) で処理できるので、全体では \(O(NMK+Q(N+M+K))\) で解けました。