CodeCraft-20 - F:Battalion Strength
解けたけど、コンテスト中のACは遠い...。
問題
考察と解法
期待値の代わりに総和を考えることにする。スコアが和の形をしているので、2つの数の積が足される集合はいくつあるかを考えよう(0-indexedとする)。といってもこれは簡単である。あらかじめを昇順にソートしておけば、との間にある数は集合内に1つも存在してはならず、他のものは自由に決められるから、条件をみたす個である。クエリが1個の場合はなんとかなりそうだ。
変更クエリが飛んでくるのが厄介だが、今述べた計算をセグ木に載せることを考える。左側の区間にはという数列があり、右側の区間はという数列があり、それぞれ昇順に並んでいるとする。また、2つの区間をマージした区間をとする。
各区間での答えがわかっていて、マージした後の答えを知りたいとしよう。については、右側に個だけ使える数が増えたので、への寄与はになる。の寄与も同様となる。問題は、という形の項をどうするかで、これはだけでは計算できない。マージ後の区間については、は回足されるわけだから、への寄与はとなる。これをについて足し合わせるわけだから、のの値とのの値がわかっていればよい。これで答えを計算するのに必要な情報は揃った。結局、各区間にもたせる値は
これらの値のみで、マージ後のこれらの値も定数時間で計算できる。これでセグ木に載せる準備が整った。
実装は、クエリを先読みし、重複する値も区別しながら各数にidを割り振るとよい。セグ木で管理する配列の長さが個になるので、定数倍には注意したい。