← 返回题目列表

Codeforces · 461/C

C. 阿普尔曼和一张纸

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

阿普尔曼有一张很大的纸。该片材呈矩形,尺寸为 1 × n。你的任务是帮助阿普尔曼折叠这样一张纸。实际上,您需要执行 q 查询。每个查询将具有以下类型之一:

1. 在位置 pi 处折叠纸张。执行此查询后,尺寸为 1 × pi 的纸张最左侧部分必须位于尺寸为 1 × ([纸张的当前宽度] - pi)的纸张最右侧部分之上。
2. 如果我们进行后面描述的两次切割并仅考虑切割之间的碎片,请计算纸片的总宽度是多少。我们将在距当前纸张左边框距离 li 处进行一次切割,并在距当前纸张左边框距离 ri 处进行另一次切割。

请查看第一个测试示例的解释,以便更好地理解问题。

输入

第一行包含两个整数:n 和 q (1 ≤ n ≤ 105; 1 ≤ q ≤ 105) — 纸张的宽度和查询数。

以下 q 行中的每一行都包含采用以下格式的所描述的查询之一:

- "1 pi" (1 ≤ pi < [当前工作表宽度]) — 第一种类型查询。
- "2 li ri" (0 ≤ li < ri ≤ [当前工作表宽度]) — 第二种类型查询。

输出

对于第二类型的每个查询,输出答案。

示例

输入 #1

7 4
1 3
1 2
2 0 1
2 1 2

输出 #1

4
3

输入 #2

10 9
2 2 9
1 1
2 0 1
1 8
2 0 8
1 2
2 1 3
1 4
2 2 4

输出 #2

7
2
10
4
5

注意

下图显示了第一个示例查询时纸张的形状:

第一次折叠操作后,纸张的宽度等于 4,第二次折叠操作后,纸张的宽度等于 2。