← 返回题目列表

AtCoder · joi2009yo_e

E. 随机播放

中文机器翻译题面 查看原题

配点: 100 点

問題

1 从 n 写有编号的卡片共有 n 张。首先,最上面是编号 1 的卡片,从上数第 2 张是编号 2 的卡片,\ldots,最下面是编号 n 的卡片,按顺序叠放,形成卡片堆。

对卡片堆进行所谓的“洗牌”(shaffuru)操作, (x, y) 可以重新排列卡片(满足x, y 是 小于或等于 1 \leqq x < y < n 的整数条件)。

沙弗鲁 (x, y)

n 从顶部开始的卡片 x 一堆牌,最多包含第一张牌, 从x + 1 页面 y B 堆由第 th 张牌组成,y + 1 页面 n 由第张牌组成的堆 C 3 分成两座山。然后,将B堆在A山的顶部,将C堆在A山的顶部。

例如,按顺序排列 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

9
1
3 7 4
3 5

出力例 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 件。