第三回 アルゴリズム実技検定 I - 行列操作
愚直に実装すると、
クエリ1,2は$ O(N)
クエリ3は$ O(N^2)
クエリ4は$ O(1)
最悪ケースで$ O(QN^2)でTLEする
クエリ3が無くても$ O(N^2)で改善が必要
クエリ3は転置フラグを持っておくことでこれを更新するだけの$ O(1)でできるようになる
表示時や更新時は転置フラグを見て行と列の操作を入れ替える
クエリ1,2も行と列のそれぞれの順番を持っておくとこれを更新するだけの$ O(1)でできるようになる
表示時はその行と列が実際には何番目の値なのかを確認する
事前に順番の準備が$ O(N)でクエリ処理が$ O(Q)で全体で$ O(N+Q)