分数: 525 点
问题陈述
有 N 数轴上的间隔,编号为 1 to N.
区间的左端点 i 位于坐标处 0,右端点位于坐标处 W_i。在这里, W_1 < W_2 < \dots < W_N.
你被给予 Q 查询;按照给定的顺序处理它们。每个查询都是以下三种类型之一:
- 类型 1 (
1 v):让 l 是当前的坐标 左端点 间隔 v。翻译每个编号的间隔 v 或更少,以便其 左端点 位于坐标处 l. - 类型 2 (
2 v):让 r 是当前的坐标 右端点 间隔 v。翻译每个编号的间隔 v 或更少,以便其 右端点 位于坐标处 r. - 类型 3 (
3 x): 输出当前包含坐标的区间数 x+\frac{1}{2}.
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq W_i \leq 10^9 (1 \leq i \leq N)
- W_1 < W_2 < \dots < W_N
- 对于 v 在类型查询中给出 1 和 2, 1 \leq v \leq N.
- 对于 x 在类型查询中给出 3, 0 \leq x \leq 10^9.
- 至少一个类型的查询 给出了 3 。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N
W_1 \dots W_N
Q
\textrm{query}_1
\textrm{query}_2
\vdots
\textrm{query}_Q
\textrm{query}_j 代表 j第一个查询。每个查询均以下列格式之一给出:
1 v
2 v
3 x
输出
让 q 是该类型的查询数 3,输出 q 行。的 j- 第行 (1 \leq j \leq q)应包含以下问题的答案 j类型的第一个查询 3.
示例输入 1
4 2 4 6 10 5 2 3 1 2 3 2 2 4 3 1
示例输出 1
4 1
最初,按编号顺序排列的间隔是 [0, 2], [0, 4], [0, 6], [0, 10].
- 对于 1st查询,坐标 右端点 间隔 3 操作前 6,所以操作后的间隔是 [4, 6], [2, 6], [0, 6], [0, 10] 按编号顺序排列。
- 对于 2nd查询,坐标 左端点 间隔 2 操作前 2,所以操作后的间隔是 [2, 4], [2, 6], [0, 6], [0, 10] 按编号顺序排列。
- 对于 3rd查询,包含坐标的区间 2 + \frac{1}{2} 是间隔 1,2,3,4,这是四个间隔,所以输出 4.
- 对于 4第次查询,坐标 右端点 间隔 4 操作前 10,所以操作后的间隔是 [8, 10], [6, 10], [4, 10], [0, 10] 按编号顺序排列。
- 对于 5第次查询,包含坐标的区间 1 + \frac{1}{2} 只是区间 4,这是一个区间,所以输出 1.