Matrix Operation (AOJ 2343)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2343

問題

N*N行列に値が入っている。行列を回転させたり、列や行をswapさせる命令や行列のある場所に値を書き込むクエリがQ個来る。全てのクエリをさばいた後に指定された部分行列のハッシュ値を求めよ。
1<=N<=40,000
1<=Q<=40,000

解法

行列の回転、上下左右の反転を8状態で表す。こうしておけば回転の処理はO(1)で可能になる。列や行のスワップは現在の状態から回転などの逆の処理をしてどの行・列がスワップされるかを計算すればこれもO(1)でできる。値を書き込む命令はmapに突っ込めばO(QlogQ)で出来る。あとは上記の物を実装すれば良い。