ABC189 E - Rotate and Flip (500)
愚直にやると
$ O(N^2)
かかり間に合わない
関数毎に計算結果を合成すると計算量が落ちそう
操作とクエリを先読みする
クエリを操作順の昇順で並べ替えておく
クエリ毎にXやYとそれぞれの加算値やXYの反転などを記憶し、その操作後の結果を見るクエリを実施する
クエリの結果は答え用の配列に保存しておく
$ O(N+M+Q \log Q)
問題:
https://atcoder.jp/contests/abc189/tasks/abc189_e
提出:
https://atcoder.jp/contests/abc189/submissions/19627326
#ABC189
#E
#500pt
#ABC
#AtCoder