AT_abc428_f.[ABC428F] Pyramid Alignment

在数轴上有 $N$ 个区间，编号从 $1$ 到 $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}$ 的区间数量。

输入由标准输入给出，格式如下：

$N$ $W_1$ $\dots$ $W_N$ $Q$
$\textrm{query}_1$
$\textrm{query}_2$
$\vdots$
$\textrm{query}_Q$

其中，第 $j$ 个操作 $\textrm{query}_j$ 的格式如下：

$1$ $v$

$2$ $v$

$3$ $x$

设类型 $3$ 的操作有 $q$ 个，对于每一次类型 $3$ 的操作，输出一行答案。第 $j$ 行（$1 \leq j \leq q$）输出第 $j$ 个类型 $3$ 操作的答案。

样例解释 1

初始时，区间依次为 $[0,2], [0,4], [0,6], [0,10]$。

• 第 $1$ 次操作前，第 $3$ 个区间的右端点坐标为 $6$。操作后区间的状态依次为 $[4,6], [2,6], [0,6], [0,10]$。
• 第 $2$ 次操作前，第 $2$ 个区间的左端点坐标为 $2$。操作后区间的状态依次为 $[2,4], [2,6], [0,6], [0,10]$。
• 第 $3$ 次操作时，包含坐标 $2+\frac{1}{2}$ 的区间为第 $1,2,3,4$ 个，共 $4$ 个区间，应输出 $4$。
• 第 $4$ 次操作前，第 $4$ 个区间的右端点坐标为 $10$。操作后区间的状态依次为 $[8,10], [6,10], [4,10], [0,10]$。
• 第 $5$ 次操作时，包含坐标 $1+\frac{1}{2}$ 的区间只有第 $4$ 个区间，共 $1$ 个区间，应输出 $1$。

数据范围

• $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$
• 类型 $1$、$2$ 操作给定的 $v$ 满足 $1 \leq v \leq N$。
• 类型 $3$ 操作给定的 $x$ 满足 $0 \leq x \leq 10^9$。
• 至少有一次类型 $3$ 的操作。
• 所有输入数据均为整数。

由 ChatGPT 5 翻译