長さNの、bool列(全部の要素が0 or 1)に対して以下のクエリがQ個飛んでくる
l, rが与えられるから, l番目~r番目の数列を切り出した時、それの転倒数を求める
l, rが与えられるから, l番目~r番目の要素を全部反転させる(0だったら1に, 1だったら0に)
N = Q = 100,000 TLE2s
という問題の解答です
ざっくり言うと遅延評価Segment Treeで解けます
区間ごとにその区間の(0の個数, 1の個数, 転倒数)を求めておきます
すると、区間のmergeが
0の個数 = はい。
1の個数 = そう。
転倒数 = (左側の区間の転倒数) + (右側の区間の転倒数) + (左側の1の個数) * (右側の0の個数)
となりOK
区間に反転しろという命令が飛んできたときは
new0の個数 = old1の個数
new1の個数 = old0の個数
new転倒数 = {(区間の長さ) C 2} - {(old0の個数) C 2} - {(old1の個数) C 2} - old転倒数
でOKです
上級編の解答
IJPC 2012 #1: 解説: 魔法の訓練(Magical Training)
とダダかぶりだった。