(問題 8)Segment Treeの区間計算2 : 区間分割 C編（paizaランク A 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ポスト
問題
下記の問題をプログラミングしてみよう！
(はじめに)
以降、s 以上 t 以下の整数の集合を [s,t] と表記します。
いままでで、特定の区間に対する計算結果が頂点に入っていることがわかりました。
それらの区間に対する結果を用いて、任意の区間 [L,R] に対する結果を計算していきます。
そのためには、[L,R] を計算結果がSegment Treeに存在する区間に分割する必要があります。
まず始めにSegment Treeで計算されている区間について確認します。
区間 [s,t] の計算結果がSegment Treeに存在するとき次の条件を満たします。詳しくは問題 7 を参照してください。
では、任意の区間 [L,R] をどのように分割すればよいでしょうか。結論から言うと以下の動作で O(log n) 個の区間に分割することが出来ます。
分割した区間を入れる配列 ans を用意する。
now を L で初期化する。
now が R を越すまで以下を繰り返す。
次の条件を満たす最大の l を見つける。
R ≧ now + 2 ** l - 1 である。 → 範囲外の要素を含まないための条件
now は 2 ** l の倍数である。 → Segment Treeに計算結果が存在するための条件
[now,now + 2 ** l - 1] を ans に加える。
now に 2 ** l を足す。
ではここではこれをプログラムに直してみましょう。
(問題)
Q 個のクエリが与えられるので順番に処理を行ってください。i 番目のクエリは以下の通りです。
- 入力される値
-
入力は以下のフォーマットで与えられます。
Q
L_1 R_1
L_2 R_2
...
L_Q R_Q
1 行目には 1 つの整数 Q が与えられます。
1 + i (1 ≦ i ≦ Q) 行目には 2 つの整数 L_i,R_i が与えられます。
入力は合計 1 + Q 行からなり、入力値最終行の末尾に改行を 1 つ含みます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
i 番目のクエリで x_i 個の区間に分割したとするとき、x_1 + x_2 + ... + x_Q + Q 行で出力してください。
それぞれのクエリに対し以下のように出力してください。- まず、区間数を 1 行で出力する。そのあと区間 [s,t] を s が小さい順に出力する。
この際、それぞれ区間を出力する際は、s,t - s + 1 を空白区切りで 1 行に出力してください。
- 条件
-
すべてのテストケースについて以下の条件を満たします。
- 1 ≦ Q ≦ 20000
- 0 ≦ L_i ≦ R_i ≦ 2 ^ 30 - 1 (1 ≦ i ≦ Q)
- 入力例1
-
5
3 9
4 8
4 7
12 18
5 20
- 出力例1
-
3
3 1
4 4
8 2
2
4 4
8 1
1
4 4
3
12 4
16 2
18 1
5
5 1
6 2
8 8
16 4
20 1
