Sparse Table の構築 Step 2 D(Beta)編（paizaランク A 相当）

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

下記の問題をプログラミングしてみよう！

説明

Sparse Table では、任意の長さの区間を 2 つの「2 べきの長さの区間」で覆うことで高速に区間最小値を求めます。
そこで、任意の長さの区間に対して、その区間を覆う同じ長さの 2 つの 2 べきの長さの区間を考えます（2 つの長さ 2^k の区間が同じでもよいとします）。
ここでいう 2 つの区間 [a,b), [c,d) が区間 [l,r) を覆うとは、[l,r) = [a,b) ∪ [c,d) を満たすことを言います。
例えば、区間 [1,7) は、長さ 2^2 = 4 の区間 [1,5) と [3,7) で覆うことができます。
長さ 2^1 = 2 の区間 2 つで区間 [1,7) を覆うことはできません。
また、区間 [0,4) と [3,7) では、余計な部分を含んでしまうため区間 [1,7) を覆うことはできません。
一般に、長さ L の区間 [l,r) を 2 つの長さ 2^k の区間で覆うには、k を 2^k ≦ L を満たす最大の k とする必要があります。

問題

Q 個のクエリが与えられるので順に解答してください。クエリの形式は以下の通りです。
・l r：区間 [l,r) を覆う 2 つの 2 べきの長さの区間を出力する。ただし、2 つの区間の長さは同じでなくてはならない。出力する 2 つの区間は同じでもよい。

例えば、区間 [1,7) を覆う 2 つの長さ 2^2 = 4 の区間は [1,5) と [3,7) です。
区間 [0,8) を覆う 2 つの長さ 2^3 = 8 の区間は [0,8) と [0,8) です。また、長さ 2^2 = 4 の区間 [0,4) と [4,8) で覆うこともできます。この場合、どちらを出力しても正解となります。

入力される値

入力は以下のフォーマットで与えられます。

Q
l_1 r_1
l_2 r_2
...
l_Q r_Q

・1 行目には、クエリの数を表す整数 Q が与えられます。
・続く Q 行の i 行目には i 個目のクエリが与えられます。クエリの形式は問題文の通りです。
・入力は合計で Q+1 行からなり、入力値最終行の末尾に改行が１つ入ります。

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力: 期待する出力は Q 行からなります。
i 行目には、i 個目のクエリで与えられる区間 [l_i,r_i) が 2 べきの長さの区間 [a_i,b_i) と区間 [c_i,d_i) で覆えるとき、この a_i, b_i, c_i, d_i を空白区切りで出力してください。
最後は改行し、余計な文字、空行を含んではいけません。

条件: すべてのテストケースにおいて、以下の条件をみたします。

・1 ≦ Q ≦ 10^5
・0 ≦ l_i < r_i ≦ 10^5

入力例1: 5
17 19
5 12
1 17
8 15
2 18

出力例1: 17 19 17 19
5 9 8 12
1 17 1 17
8 12 11 15
2 18 2 18

入力例2: 8
5 6
3 7
21 23
25 39
6 38
15 47
2 35
35 36

出力例2: 5 6 5 6
3 7 3 7
21 23 21 23
25 33 31 39
6 38 6 38
15 47 15 47
2 34 3 35
35 36 35 36

入力例3: 10
99776 99840
21183 49691
53213 54404
23108 39920
26884 59652
54648 87928
62373 70565
94159 94175
5853 18140
55201 55202

出力例3: 99776 99840 99776 99840
21183 37567 33307 49691
53213 54237 53380 54404
23108 39492 23536 39920
26884 59652 26884 59652
54648 87416 55160 87928
62373 70565 62373 70565
94159 94175 94159 94175
5853 14045 9948 18140
55201 55202 55201 55202

問題一覧へ戻る