CF477E.Dreamoon and Notepad

Dreamoon 刚刚用 notepad.exe 创建了一个困难题目的文档。该文档由 $n$ 行文本组成，第 $i$ 行的长度为 $a_{i}$。现在他想知道在这么长的文档中，如何以最快的方式移动光标。

记 $ (r, c) $ 为当前光标的位置，其中 $r$ 是行号，$c$ 是该行中的光标位置。满足 $1 \leq r \leq n$，$0 \leq c \leq a_{r}$。

在 notepad.exe 中，假设当前光标在 $ (r, c) $，我们可以用如下六种操作移动光标：

1. 上键（up）：新的光标位置 $ (nr, nc) = (\max(r-1,1), \min(a_{nr}, c)) $
2. 下键（down）：新的光标位置 $ (nr, nc) = (\min(r+1, n), \min(a_{nr}, c)) $
3. 左键（left）：新的光标位置 $ (nr, nc) = (r, \max(0, c-1)) $
4. 右键（right）：新的光标位置 $ (nr, nc) = (r, \min(a_{nr}, c+1)) $
5. HOME 键：新的光标位置 $ (nr, nc) = (r, 0) $
6. END 键：新的光标位置 $ (nr, nc) = (r, a_{r}) $

你将得到文档的描述（$n$ 和数列 $a_{i}$），以及 Dreamoon 的 $q$ 个询问。每个询问会给出一个起始光标位置 $ (r_{1}, c_{1}) $ 和目标光标位置 $ (r_{2}, c_{2}) $，询问将光标从 $ (r_{1}, c_{1}) $ 移动到 $ (r_{2}, c_{2}) $ 至少需要多少次按键。

第一行为一个整数 $n$（$1 \leq n \leq 10^5$），表示文本的行数。

第二行为 $n$ 个整数 $a_{1}, a_{2}, \ldots, a_{n}$，其中 $a_{i}$ 表示第 $i$ 行的长度（$0 \leq a_{i} \leq 10^6$）。

第三行为一个整数 $q$，表示询问的数量（$1 \leq q \leq 10^5$）。

接下来的 $q$ 行，每行四个整数 $r_{1}, c_{1}, r_{2}, c_{2}$，表示一次询问：初始光标在第 $r_{1}$ 行第 $c_{1}$ 个位置，目标为第 $r_{2}$ 行第 $c_{2}$ 个位置。保证 $1 \leq r_{1}, r_{2} \leq n$，$0 \leq c_{1} \leq a_{r_{1}}$，$0 \leq c_{2} \leq a_{r_{2}}$。

对于每个询问，输出该询问的答案，即最少的按键次数，每行一个结果。

在第一个样例中，第一个询问可以通过依次按下 HOME、right 按键完成。

第二个询问可以通过依次按下 down、down、down、END、down 完成。

第三个询问可以通过依次按下 down、END、down 完成。

第四个询问可以通过依次按下 END、down 完成。

由 ChatGPT 5 翻译