yukicoder 1338 Giant Class

愚直に座れる席を管理すると$ O(HW + Q)となり間に合わない. またこれを少し工夫すると各列ごとに座れる席を管理しておくという方法が思いつくが, これでも$ O(W + Q)かかり間に合わない.

実はこの方法を少し改善することで$ O(Q log Q)で解くことができる. 具体的には, 座れる席に変化があるのは高々$ O(Q)列のみなのでmapなどのデータ構造を持つことにより高速に処理することができる.