AT_abc365_f [ABC365F] Takahashi on Grid

平面上有无限多个格子。对于所有整数二元组 $(x, y)$，都存在一个对应的格子，称为格子 $(x, y)$。 每个格子要么是空格子，要么是墙格子。 给定长度为 $N$ 的正整数序列 $L = (L_1, L_2, \dotsc, L_N)$，$U = (U_1, U_2, \dotsc, U_N)$。其中，对于 $i = 1, 2, \ldots, N$，有 $1 \leq L_i \leq U_i \leq 10^9$。 满足 $1 \leq x \leq N$ 且 $L_x \leq y \leq U_x$ 的格子 $(x, y)$ 都是空格子，其余格子都是墙格子。 当高桥君在空格子 $(x, y)$ 时，可以进行以下任一操作： - 如果格子 $(x+1, y)$ 是空格子，则可以移动到 $(x+1, y)$。 - 如果格子 $(x-1, y)$ 是空格子，则可以移动到 $(x-1, y)$。 - 如果格子 $(x, y+1)$ 是空格子，则可以移动到 $(x, y+1)$。 - 如果格子 $(x, y-1)$ 是空格子，则可以移动到 $(x, y-1)$。 保证任意两个空格子之间都可以通过若干次操作互相到达。 请回答 $Q$ 个如下形式的询问。 对于第 $i$ 个询问 $(1 \leq i \leq Q)$，给定整数四元组 $(s_{x,i}, s_{y,i}, t_{x,i}, t_{y,i})$，请你求出高桥君从格子 $(s_{x,i}, s_{y,i})$ 移动到格子 $(t_{x,i}, t_{y,i})$ 所需的最小操作次数。保证每个询问给定的两个格子都是空格子。

输入按以下格式从标准输入读入。 > $N$ > $L_1$ $U_1$ > $L_2$ $U_2$ > $\vdots$ > $L_N$ $U_N$ > $Q$ > $s_{x,1}$ $s_{y,1}$ $t_{x,1}$ $t_{y,1}$ > $s_{x,2}$ $s_{y,2}$ $t_{x,2}$ $t_{y,2}$ > $\vdots$ > $s_{x,Q}$ $s_{y,Q}$ $t_{x,Q}$ $t_{y,Q}$

输出 $Q$ 行，第 $i$ 行输出第 $i$ 个询问的答案。

### 数据范围 - $1 \leq N \leq 2 \times 10^5$ - $1 \leq L_i \leq U_i \leq 10^9\ (1 \leq i \leq N)$ - $[L_i, U_i] \cap [L_{i+1}, U_{i+1}] \neq \emptyset\ (1 \leq i < N)$ - $1 \leq Q \leq 2 \times 10^5$ - $1 \leq s_{x,i} \leq N$ 且 $L_{s_{x,i}} \leq s_{y,i} \leq U_{s_{x,i}}\ (1 \leq i \leq Q)$ - $1 \leq t_{x,i} \leq N$ 且 $L_{t_{x,i}} \leq t_{y,i} \leq U_{t_{x,i}}\ (1 \leq i \leq Q)$ - 输入均为整数 ### 样例解释 1 给定的格子如下图所示。  对于第 $1$ 个询问，例如可以如下移动，从格子 $(1,4)$ 经过 $10$ 次操作到达格子 $(6,3)$。  无法用 $9$ 次或更少的操作从 $(1,4)$ 到 $(6,3)$，因此应输出 $10$。 ### 样例解释 2 注意输出的值可能超出 $32$ 位整数范围。 由 ChatGPT 4.1 翻译