AT_arc193_a [ARC193A] Complement Interval Graph

对于整数 $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$ 如下： - 图包含编号为 $1, 2, \ldots, N$ 的 $N$ 个顶点。 - 对于所有 $i, j \in [1, N]$，当且仅当区间 $[L_i, R_i]$ 与 $[L_j, R_j]$ 的交集为空时，顶点 $i$ 与顶点 $j$ 之间存在一条无向边。 此外，对于 $i = 1, 2, \ldots, N$，定义顶点 $i$ 的权重为 $W_i$。 给定与图 $G$ 相关的 $Q$ 个查询，请按顺序处理这些查询。对于第 $i = 1, 2, \ldots, Q$ 个查询，其形式如下： > 给定满足 $s_i \neq t_i$ 的整数 $s_i, t_i$（$1 \leq s_i, t_i \leq N$）。判断在图 $G$ 中是否存在从顶点 $s_i$ 到顶点 $t_i$ 的路径。若存在，则输出该路径的**权重**的最小值。 此处，从顶点 $s$ 到顶点 $t$ 的路径权重定义为该路径上所有顶点（包括端点 $s$ 和 $t$）的权重之和。

输入通过标准输入给出，格式如下： > $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$ 行，若顶点 $s_i$ 到顶点 $t_i$ 的路径存在，则输出其最小权重；否则输出 `-1`。

### 约束条件 - $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$ - 输入中的所有值均为整数 ### 样例解释 1 图 $G$ 包含以下 4 条无向边：$\lbrace 1, 3 \rbrace$、$\lbrace 2, 3 \rbrace$、$\lbrace 2, 4 \rbrace$、$\lbrace 3, 4 \rbrace$。 - 对于第 1 个查询，存在路径 $1 \to 3 \to 4$，其权重为 $W_1 + W_3 + W_4 = 5 + 4 + 2 = 11$，为最小可能值。 - 对于第 2 个查询，存在路径 $4 \to 3$，其权重为 $W_4 + W_3 = 2 + 4 = 6$，为最小可能值。 - 对于第 3 个查询，顶点 5 到顶点 2 之间不存在路径，因此输出 `-1`。 翻译由 DeepSeek R1 完成