CodeCraft-20 - F:Battalion Strength

解けたけど、コンテスト中のACは遠い...。

問題

codeforces.com

考察と解法

 期待値の代わりに総和を考えることにする。スコアが和の形をしているので、2つの数の積 p _ i p _ jが足される集合はいくつあるかを考えよう(0-indexedとする)。といってもこれは簡単である。あらかじめ pを昇順にソートしておけば、 ijの間にある数は集合内に1つも存在してはならず、他のものは自由に決められるから、条件をみたす2 ^ {i + N-j-1}個である。クエリが1個の場合はなんとかなりそうだ。
 変更クエリが飛んでくるのが厄介だが、今述べた計算をセグ木に載せることを考える。左側の区間Lにはp _ 0, p _ 1,\cdots, p _ {n-1}という数列があり、右側の区間Rq _ 0, q _ 1,\cdots, q _ {m-1}という数列があり、それぞれ昇順に並んでいるとする。また、2つの区間をマージした区間Iとする。
 各区間での答えval _ L,val _ Rがわかっていて、マージした後の答えval _ Iを知りたいとしよう。val _ Lについては、右側にm個だけ使える数が増えたので、val _ Iへの寄与は 2 ^ mになる。 val _ Rの寄与も同様となる。問題は、p _ i q _ jという形の項をどうするかで、これはval _ L,val _ Rだけでは計算できない。マージ後の区間については、 p _ i q _ j2 ^ {i+m-j-1}回足されるわけだから、val _ Iへの寄与は p _ i q _ j 2 ^ {i+m-j-1} = p _ i 2 ^ i \times q _ j 2 ^{m-j-1}となる。これをi,jについて足し合わせるわけだから、 L \sum _ i  p _ i 2 ^ iの値と R \sum _  j q _ j 2 ^{m-j-1}の値がわかっていればよい。これで答えを計算するのに必要な情報は揃った。結局、各区間にもたせる値は

これらの値のみで、マージ後のこれらの値も定数時間で計算できる。これでセグ木に載せる準備が整った。
 実装は、クエリを先読みし、重複する値も区別しながら各数にidを割り振るとよい。セグ木で管理する配列の長さがN+Q個になるので、定数倍には注意したい。

実装

codeforces.com