ABC172 F - Unfair Nim (600)
Nimなので全ての山の石のXORを0にしたい
$ A_3以降の山は先にXORを求めて$ Xとしてまとめておく
なので、Nは$ 10^7とかでも問題ない
$ A_1を$ lに、$ A_2を$ rにする
それぞれのbit毎に見ていく
Xのそのbitが1の場合、ひとまず$ rにそのbitを立てる
0の場合、そのbitが必要か分からないので後回し
$ l+rを求めて、本来の値になるのに必要な値の差分を持っておく
それぞれのbitを上から見ていく
そのbitで$ l, rの両方のbitが立っておらず、両方立てる余裕がある場合は両方のbitを立てる
$ lを最大化するためにそれぞれのbitを上から見ていく
$ rでだけbitが立っていて、そのbitを$ lに代わりに立てても$ l \le A_1のままならbitを移行する
問題文の条件を満たしているか確認するため以下を全てチェック(いくつかはたぶん不要)
$ l + r = A_1 + A_2
$ l \oplus r = X
$ l \gt 0かつ$ l \le A_0かつ$ r \ge A_2
$ A_0 - lが必要な移動すべき石の数
それぞれbit毎に見ているだけなので$ O(N + \log A)