AT_arc196_d [ARC196D] Roadway

有 $N$ 个城镇，编号为 $1,2,\ldots,N$，这些城镇按顺序排成一列。 此外，有 $N-1$ 条道路，每条道路连接相邻的两个城镇。第 $j$ 条道路（$1\leq j\leq N-1$）连接城镇 $j$ 和城镇 $j+1$。你可以为每条道路 $j$ 设置一个**强度** $w_j$（可以为负数的整数）。 当一个人通过一条道路时，他的**体力**会发生变化。具体来说，体力为 $x$ 的人在通过第 $j$ 条道路后，体力会变为 $x+w_j$。 接下来有 $M$ 个人要在城镇之间移动。 第 $i$ 个人（$1\leq i\leq M$）从体力为 $0$ 的状态下，从城镇 $S_i$ 出发，沿最短路径前往城镇 $T_i$。这里保证 $|S_i-T_i|>1$。另外，若 $i\neq j$，则 $(S_i,T_i)\neq (S_j,T_j)$。 第 $i$ 个人的要求如下： > 当他从城镇 $S_i$ 出发和到达城镇 $T_i$ 时，体力恰好为 $0$，在其他经过的城镇时，体力始终为正整数。 此外，除了通过道路导致的体力变化外，体力不会有其他变化。 请处理 $Q$ 个询问。对于第 $k$ 个询问（$1\leq k\leq Q$），如果存在一种道路强度的设置方法，能满足第 $L_k,L_k+1,\ldots,R_k$ 个人的所有要求，则输出 `Yes`，否则输出 `No`。

输入按以下格式从标准输入给出。 > $N$ $M$ $Q$ > $S_1$ $T_1$ > $S_2$ $T_2$ > $\vdots$ > $S_M$ $T_M$ > $L_1$ $R_1$ > $L_2$ $R_2$ > $\vdots$ > $L_Q$ $R_Q$

输出 $Q$ 行。 第 $k$ 行输出 `Yes`，如果存在一种道路强度的设置方法，能满足第 $L_k,L_k+1,\ldots,R_k$ 个人的所有要求；否则输出 `No`。

### 数据范围 - $3\leq N\leq 4\times 10^5$ - $1\leq M\leq 2\times 10^5$ - $1\leq Q\leq 2\times 10^5$ - $1\leq S_i,T_i\leq N$ - $|S_i-T_i|>1$ - $(S_i,T_i)\neq (S_j,T_j)\ (i\neq j)$ - $1\leq L_k\leq R_k\leq M$ - 所有输入均为整数 ### 样例解释 1 对于第 $1$ 个询问，考虑将道路 $1,2,3,4$ 的强度分别设置为 $1,-1,1,-1$。此时，第 $1$ 个人从城镇 $4$ 出发，体力为 $0$，到达城镇 $3$ 时体力为 $1$，到达城镇 $2$ 时体力为 $0$。第 $2$ 个人从城镇 $1$ 出发，体力为 $0$，到达城镇 $2$ 时体力为 $1$，到达城镇 $3$ 时体力为 $0$。第 $3$ 个人从城镇 $3$ 出发，体力为 $0$，到达城镇 $4$ 时体力为 $1$，到达城镇 $5$ 时体力为 $0$。因此，这种设置方法能满足第 $1,2,3$ 个人的所有要求，所以第 $1$ 行输出 `Yes`。对于第 $2$ 个询问，不可能满足第 $2,3,4$ 个人的所有要求，因此输出 `No`。 由 ChatGPT 4.1 翻译