← 返回题目列表

AtCoder · abc365_f

I. 网格上的高桥

中文机器翻译题面 查看原题

分数: 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