← 返回题目列表

AtCoder · arc193_a

A. 补区间图

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

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