E - シャッフル (original) (raw)
E - シャッフルEditorial 
/ 
Time Limit: 10 sec / Memory Limit: 256 MB
配点： 100 点
問題
1 から n までの番号が書かれた n 枚のカードがある．まず，一番上が番号 1 のカード，上から 2 枚目が番号 2 のカード，\ldots，一番下が番号 n のカードとなるように順番に重ねて，カードの山を作る．
カードの山に対して，「シャッフル (x, y) 」と呼ばれる次のような操作を行うことで，カードを並び替える（x, y は 1 \leqq x < y < n をみたす整数）．
シャッフル (x, y)
n 枚のカードを，一番上から x 枚目までのカードからなる山 A，x + 1 枚目から y 枚目のカードからなる山 B，y + 1 枚目から n 枚目のカードからなる山 C の 3 つの山に分ける．そして，山 A の上に山 B を重ね，さらにその上に山 C を重ねる．
例えば，順番に並んでいる 9 枚のカードに対して「シャッフル (3, 5)」を行うと，9 枚のカードに書かれた番号は，上から順番に 6, 7, 8, 9, 4, 5, 1, 2, 3 となる．
最初の山の状態から m 回のシャッフル「シャッフル (x_1, y_1)」「シャッフル (x_2, y_2)」\cdots「シャッフル (x_m, y_m)」を順番に行った後のカードの山において，上から数えて p 枚目から q 枚目のカードの中に番号が r 以下のカードが何枚含まれているかを求めるプログラムを作成せよ．
入力
入力は m + 3 行からなる．1 行目にはカードの枚数 n が書かれている (3 \leqq n \leqq 1\,000\,000\,000 = 10^9) ．2 行目にはシャッフルの回数を表す整数 m が書かれている (1 \leqq m \leqq 5000)．3 行目には整数 p, q, r が書かれている (1 \leqq p \leqq q \leqq n，1 \leqq r \leqq n)．i + 3 行目 (1 \leqq i \leqq m) には 2 つの整数 x_i, y_i (1 \leqq x_i < y_i < n) が空白を区切りとして書かれている．
出力
m 回のシャッフル後のカードの山において，上から数えて p 枚目から q 枚目のカードの中に含まれている番号が r 以下のカードの枚数を出力せよ．
出力例 1
2
入力例 1 の山に対して, 「シャッフル (3, 5)」を行うと，カードは上から順番に 6, 7, 8, 9, 4, 5, 1, 2, 3 となる．上から数えて 3 枚目から 7 枚目に含まれる番号が 4 以下のカードは，番号 4 と番号 1 の 2 枚である．
入力例 2
12 3 3 8 5 3 8 2 5 6 10
出力例 2
3
入力例 2 の山に対して, 「シャッフル (3, 8)」「シャッフル (2, 5)」「シャッフル (6, 10)」を順番に行うと，カードは上から順番に 9, 10, 3, 11, 12, 4, 5, 6, 7, 8, 1, 2 となる．上から数えて 3 枚目から 8 枚目に含まれる番号が 5 以下のカードは 3 枚である．