分数: 575 点
问题陈述
平面上有无限多个单元。 对于每对整数 (x,y),有一个对应的cell,我们称之为cell (x,y).
每个单元格要么是空单元格,要么是壁单元格。
给定两个长度为正整数的序列 N: L=(L _ 1,L _ 2,\dotsc,L _ N) 和 U=(U _ 1,U _ 2,\dotsc,U _ N)。
在这里, L _ i 和 U _ i 满足 1\leq L _ i\leq U _ i\leq10 ^ 9 为 i=1,2,\ldots,N.
所有单元格 (x,y)\ (1\leq x\leq N,L _ x\leq y\leq U _ x) 是空单元格,所有其他单元格都是壁单元格。
当高桥处于空牢房时 (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})。 对于每个查询,保证给定的两个单元格是空单元格。
约束
- 1\leq N\leq2\times10 ^ 5
- 1\leq L _ i\leq U _ i\leq10 ^ 9\ (1\leq i\leq N)
- \lbrack L _ i,U _ i\rbrack\cap\lbrack L _ {i+1},U _ {i+1}\rbrack\neq\emptyset\ (1\leq i\lt N)
- 1\leq Q\leq2\times10 ^ 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)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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第行 (1\leq i\leq Q) 应包含以下问题的答案 i-第一个查询。
示例输入 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
给定的单元格如下。

对于第一个查询,例如,Takahashi 可以从单元格移动 (1,4) 到单元格 (6,3) 十项行动如下。

无法从单元格中移动 (1,4) 到单元格 (6,3) 九个或更少的动作,所以打印 10.
示例输入 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
请注意,输出值可能不适合 32位整数。
示例输入 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