← 返回题目列表

AtCoder · abc428_f

I. 金字塔对齐

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

分数: 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.