CodeForces #276_Div2 : C. Bits
問題
n回クエリが投げられる。(各クエリはLとRからなる)
L〜R間の整数で、bitの立っている数が最大となるような最小の値を求めよ。
解法
Rの上限がと大きいため、LからRへ値を1ずつ増やしながら
範囲内全ての値のbitをカウントする方法では間に合わない。
Lをベースになるべく値が増えないようにbitを立てたいので、Lの右端から順にbitを立てていけばよい。
計算量はとなる。
n回クエリが投げられる。(各クエリはLとRからなる)
L〜R間の整数で、bitの立っている数が最大となるような最小の値を求めよ。
Rの上限がと大きいため、LからRへ値を1ずつ増やしながら
範囲内全ての値のbitをカウントする方法では間に合わない。
Lをベースになるべく値が増えないようにbitを立てたいので、Lの右端から順にbitを立てていけばよい。
計算量はとなる。