問題一覧 > 通常問題

No.1742 Binary Indexed Train

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 76
作問者 : ShirotsumeShirotsume / テスター : 👑 KazunKazun nok0nok0
2 ProblemId : 7162 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-11-12 21:14:25

問題文

YukiCoder国を東西に結ぶ「Yuki鉄道」の路線には、西から東へ一直線状に $2^N + 1$ 個の駅が並んでおり、駅には西から $0, 1, 2, \dots 2^N$ と番号がついています。

また、Yuki鉄道では $N + 1$ 種類の列車が運行しており、列車には $0$ 号列車、 $1$ 号列車、 $\dots$ $N$ 号列車と名前がついています。

$ 0 \leq i \leq N $ である $i$ について、 $i$ 号列車は番号が $2^i$ の倍数である駅にのみ停車します。

すべての列車は西から東へ運行し、始点が駅 $0$ で、終点が駅 $2^N$ です。東から西へ向かう列車はありません。

Yuki鉄道の利用客は、現在いる駅に停車する種類の列車に乗ることができます。また、乗っている列車が停車した時、降りることができます。乗り降りは何度でも可能です。

さて、今日は $Q$ 人の利用客がYuki鉄道を利用します。$ 1 \leq i \leq Q $ である $i$ について、$i$ 番目の利用客は駅 $S_i$ から $T_i$ へ移動しようと考えています。

それぞれの利用客について、以下の問題を解いてください。


    問題:出発地の駅 $S_i$ から到着地の駅 $T_i$ への乗り継ぎを最適に行った場合、到着地を含めて移動過程で停車する駅の数として考えられる最小値を求めてください。

制約

  • 入力は全て整数
  • $ 1 \leq N \leq 60 $
  • $ 1 \leq Q \leq 10^5$
  • $ 0 \leq S_i < T_i \leq 2^N $

入力

入力は以下の形式で標準入力から与えられる。
$N$ $Q$
$S_1$ $T_1$
$S_2$ $T_2$
$\vdots$
$S_Q$ $T_Q$

$1$ 行目に $N, Q$ が空白区切りで与えられる。

$2$ 行目から、 $Q$ 行にわたって $S_i, T_i$ が空白区切りで与えられる。

出力

$Q$ 行にわたって出力せよ。 $i$ 行目には、 $i$ 番目の利用客についての問題の答えを出力せよ。 最後に改行すること。

サンプル

サンプル1
入力
3 4
1 7
3 6
2 3
5 8
出力
4
2
1
2


上の図では、左から順に駅 $0, 1, 2 ... 8$ を図示しており、下から順に $0$ 号、$1$ 号、 $2$ 号、$3$ 号列車の停車する駅を黒く塗って表しています。

また、利用客 $1, 2, 3, 4$ の最適な移動方法をそれぞれオレンジ色、水色、黄色、紫色の線で表しています。

それぞれの利用客が最適に移動した際の移動経路を以下に示します。

  • 利用客 $1$ (オレンジ): 駅 $1$ → 駅 $2$ → 駅 $4$ → 駅 $6$ → 駅 $7$
  • 利用客 $2$ (水): 駅 $3$ → 駅 $4$ → 駅 $6$
  • 利用客 $3$ (黄): 駅 $2$ → 駅 $3$
  • 利用客 $4$ (紫): 駅 $5$ → 駅 $6$ → 駅 $8$

出発地は答えに含まれないこと、現在いる駅よりも番号の小さい駅へ移動する方法が存在しないことに注意してください。

サンプル2
入力
1 2
0 2
1 2
出力
1
1

サンプル3
入力
32 5
510479020 902533247
494473032 2564665701
1753815 4290493471
3925045722 4058246871
1578437576 3200987099
出力
29
30
43
29
36

入力は 32-bit 整数型に収まらない場合があります。注意してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。