Codeforces 305C
問題
n個の非負の整数a1,a2,...,anが与えられる。
これを2^a1,2^a2,...と書き直して総和を求める。
これに2^b(b>=0)形式のものをいくつか加えて、その総和が2^{v}-1(vは任意)になるようにしたい。
いくつ加えればよいか。
1<=n<=10^5
0<=a_{i-1}<=a_i<=2*10^9
考え方
各ビットで考えられる。
a_iが来るたびに、以下を処理。メモはmapなどで。(ただし適時処理が終わったビットやビットが0のものをeraseしないと木が大きくなってTLEする。)
・a_iとa_{i-1}が違う場合
a_{i-1}からa_iまでの間にあるビットが0のものを数え上げる。
・a_iとa_{i-1}が等しい場合
桁の繰り上げが発生するので、繰り上がる桁をメモしておく。
最後に、a_n以上のビットで、最大のビットまででビットが0のものを数えればよい。(数えるべき桁数からビットが1のものを引いて求める。)
