ACM 1209. 1, 10, 100, 1000...

I am not sure about the pattern in here but we can do it with recovering the sequence. indeed the query can be up to 2^32 where we can't keep the full sequence but just because it consists of only 1s and 0s, we can only keep the positions of 1s. In C++ the STL container map can handle this situation. So how do we do it, the first one is 1. The second one is also 1. Then the next 1 can be found by jumping form the previous one 2 steps. Then 3, then 4, .... We can do it until we calculate all the 1s up to 2^32 which is not too long in our case, it will be a little more than sqrt(N).

       FULL SOURCE CODE