第８回日本情報オリンピック予選 E - シャッフル

問題概要

　1からnまでの番号が書かれたカードがこの順に重なって並んでいる。シャッフルをするクエリが与えられるから、全てのクエリを消化した後のカードの束のp枚目からq枚目の内に含まれている書かれている番号がr以下のカードの枚数を求める。

解法

　nの最大値が $10^9$ なので愚直に配列として持ってシャッフルしていくことはできない。ここでmの最大値が5000ということに注目すると、カードの情報を[1,n]の様に区間として持っておくことによって(先ほどの例は初期状態の1からnがこの順に並んでいる状態)、クエリを全消化しても区間の数はそこまで大きくならないことが分かる(例えば、n=9でシャッフル(2,4)を実行すると、([5,9][3,4][1,2])の様になる)。