今日の典型データ構造(解答編)

yosupo.hatenablog.com

長さ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)
とダダかぶりだった。