分数: 700 点
问题陈述
对于整数 l, r,让 [l, r] 表示来自的所有整数的集合 l 通过 r。也就是说, [l, r] = \lbrace l, l+1, l+2, \ldots, r-1, r\rbrace.
你被给予 N 整数对 (L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N)。 基于这些对,考虑一个无向图 G 定义如下:
- 它有 N 顶点编号 1, 2, \ldots, N.
- 对于所有人 i, j \in [1, N],顶点之间有一条无向边 i 和 j 当且仅当交集 [L_i, R_i] 和 [L_j, R_j] 为空。
此外,对于每个 i = 1, 2, \ldots, N,定义顶点的权重 i 是 W_i.
你被给予 Q 查询 G。按照给出的顺序处理这些查询。 对于每个 i = 1, 2, \ldots, Q, i第一个查询如下:
给你整数 s_i 和 t_i (两者之间 1 和 N,包括)使得 s_i \neq t_i。判断是否存在从顶点出发的路径 s_i 到顶点 t_i in G。如果存在,则打印最小可能的值 重量 这样的路径。
这里,从顶点开始的路径的权重 s 到顶点 t 被定义为该路径上顶点的权重之和(包括两个端点) s 和 t).
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq W_i \leq 10^9
- 1 \leq L_i \leq R_i \leq 2N
- 1 \leq s_i, t_i \leq N
- s_i \neq t_i
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N W_1 W_2 \cdots W_N L_1 R_1 L_2 R_2 \vdots L_N R_N Q s_1 t_1 s_2 t_2 \vdots s_Q t_Q
输出
打印 Q 行。
对于每个 i = 1, 2, \ldots, Q,在 i- 第行,如果存在从顶点开始的路径 s_i 到顶点 t_i,打印这样一条路径的最小可能权重,并打印 -1 否则。
示例输入 1
5 5 1 4 2 2 2 4 1 2 7 8 4 5 2 7 3 1 4 4 3 5 2
示例输出 1
11 6 -1
G 是一个具有四个无向边的图: \lbrace 1, 3\rbrace, \lbrace 2, 3\rbrace, \lbrace 2, 4\rbrace, \lbrace 3, 4\rbrace.
- 对于第一个查询,有一条从顶点开始的路径 1 到顶点 4 由以下给出 1 \to 3 \to 4。这条路径的权重是 W_1 + W_3 + W_4 = 5 + 4 + 2 = 11,这是可能的最小值。
- 对于第二个查询,有一条从顶点开始的路径 4 到顶点 3 由以下给出 4 \to 3。这条路径的权重是 W_4 + W_3 = 2 + 4 = 6,这是可能的最小值。
- 对于第三个查询,没有来自顶点的路径 5 到顶点 2。因此,打印
-1.
示例输入 2
8 44 75 49 4 78 79 12 32 5 13 10 16 6 8 6 15 12 15 5 7 1 15 1 2 5 5 6 3 2 7 5 4 5 5 4
示例输出 2
157 124 -1 114 114