AT_joi2024ho_d プレゼント交換 (Gift Exchange)

JOI 学园有 $N$ 名学生，每名学生被编号为 $1$ 到 $N$。 在 JOI 学园，将要举行一场交换礼物会。每位学生都准备了一份礼物，学生 $i$（$1\leq i\leq N$）将要带去的礼物的价值为 $A_i$。学生们不喜欢收到比自己带去的礼物价值低太多的礼物。具体来说，如果学生 $i$ 收到价值小于 $B_i$ 的礼物，他会感到不满。这里保证 $B_i < A_i$。 但是，不一定所有 $N$ 名学生都会参加交换会。JOI 学园的校长 K 计划考虑 $Q$ 个可能的参会学生小组，第 $j$ 个小组（$1\leq j\leq Q$）包含 $R_j-L_j+1$ 名学生，即编号为 $L_j, L_j+1, \dots, R_j$ 的学生。 对于某个包含至少 $2$ 人的学生小组，如果存在一种方式，让组内的大家交换礼物时，没有人收到自己带来的礼物，且每个人拿到的礼物价值不少于自己接收的下限（不会感到不满），那么称这个小组是“可交换礼物小组”。更具体地，若一个有 $m$ 名学生（$m\geq 2$），编号为 $p_1,p_2,\dots,p_m$ 的小组，存在一个这 $m$ 个学生的重排 $q_1,q_2,\dots,q_m$，满足以下两个条件，则认为这是一个“可交换礼物小组”。其中 $q_k$（$1\leq k\leq m$）表示把礼物交给学生 $p_k$ 的是学生 $q_k$： - 对所有 $k$（$1\leq k\leq m$），都有 $p_k \neq q_k$。 - 对所有 $k$（$1\leq k\leq m$），都有 $A_{q_k} \geq B_{p_k}$。 K 校长希望交换会能顺利举办，请你判断给定的每个小组是否为“可交换礼物小组”。 给定所有学生信息和小组信息，请编写程序判断每个小组是否“可交换礼物小组”。 ---

输入按以下格式从标准输入读入。 > $N$ $A_1$ $A_2$ $\cdots$ $A_N$ $B_1$ $B_2$ $\cdots$ $B_N$ $Q$ $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_Q$ $R_Q$

请按顺序输出 $Q$ 行。第 $j$ 行（$1\leq j\leq Q$）若第 $j$ 个小组为“可交换礼物小组”输出 `Yes`，否则输出 `No`。 ---

## 小课题 1.（$4$ 分）$N \leq 10$，$Q \leq 10$。 2.（$5$ 分）$N \leq 18$，$Q \leq 10$。 3.（$10$ 分）$N \leq 100\,000$，$A_1 \geq 2N-2$，$B_1=1$，$Q=1$，$L_1=1$，$R_1=N$。 4.（$31$ 分）$N \leq 100\,000$，$Q \leq 10$。 5.（$8$ 分）$N \leq 100\,000$，$A_i < A_{i+1}$，$B_i < B_{i+1}$（$1\leq i\leq N-1$）。 6.（$12$ 分）$N \leq 100\,000$，$A_i < A_{i+1}$（$1\leq i\leq N-1$）。 7.（$18$ 分）$N \leq 100\,000$。 8.（$12$ 分）无其他附加约束。 --- ## 样例说明 1 第 $1$ 个小组包含 $3,4$ 两名学生。若 $3$ 号学生拿到 $4$ 号学生的礼物，$4$ 号学生拿到 $3$ 号学生的礼物，则 $A_3\geq B_4$ 并且 $A_4\geq B_3$，都不会有人不满。因此，这个小组是可交换礼物小组，第 $1$ 行输出 `Yes`。 第 $2$ 个小组包含 $1,2,3$ 三名学生。由于 $A_1 < B_2$ 且 $A_3 < B_2$，$2$ 号学生无论拿到 $1$ 还是 $3$ 号学生的礼物都会感到不满。因此，这个小组不是可交换礼物小组，第 $2$ 行输出 `No`。 第 $3$ 个小组包含 $1,2,3,4$ 四名学生。比如，$1$ 号拿 $2$ 号的礼物，$2$ 号拿 $4$ 号的礼物，$3$ 号拿 $1$ 号的礼物，$4$ 号拿 $3$ 号的礼物，都不会有人不满。因此，这个小组是可交换礼物小组，第 $3$ 行输出 `Yes`。 该输入样例满足小课题 $1,2,4,7,8$ 的限制条件。 --- ## 样例说明 2 该输入样例满足小课题 $1,2,3,4,7,8$ 的限制条件。 --- ## 样例说明 3 该输入样例满足小课题 $1,2,4,5,6,7,8$ 的限制条件。 --- ## 样例说明 4 该输入样例满足小课题 $1,2,4,6,7,8$ 的限制条件。 # 数据范围 - $2 \leq N \leq 500\,000$。 - $1 \leq B_i < A_i \leq 2N$（$1\leq i\leq N$）。 - $A_1,B_1,A_2,B_2,\dots,A_N,B_N$ 均互不相同。 - $1 \leq Q \leq 200\,000$。 - $1 \leq L_j < R_j \leq N$（$1\leq j\leq Q$）。 - 所有输入均为整数。 由 ChatGPT 5 翻译