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

输入 #1

7
1 5
3 3
1 3
1 1
1 4
2 4
3 5
3
1 4 6 3
1 4 1 1
7 5 1 5

输出 #1

10
3
14

输入输出样例 #2

输入 #2

12
1 1000000000
1000000000 1000000000
1 1000000000
1 1
1 1000000000
1000000000 1000000000
1 1000000000
1 1
1 1000000000
1000000000 1000000000
1 1000000000
1 1
1
1 1 12 1

输出 #2

6000000005

输入输出样例 #3

输入 #3

10
1694 7483
3396 5566
2567 6970
1255 3799
2657 3195
3158 8007
3368 8266
1447 6359
5365 8614
3141 7245
15
3 3911 6 4694
7 5850 10 4641
1 5586 6 4808
2 3401 8 2676
3 3023 6 6923
8 4082 3 6531
6 3216 7 6282
8 5121 8 3459
8 4388 1 6339
6 6001 3 6771
10 5873 8 5780
1 6512 6 6832
8 5345 7 4975
10 4010 8 2355
7 5837 9 6279

输出 #3

2218
1212
4009
1077
3903
4228
3067
1662
4344
6385
95
6959
371
4367
444

说明/提示

数据范围

• $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 翻译