[AdditionalFile4092.zip](file://AdditionalFile4092.zip?type=additional_file)

#4092. 「JOI 2024 Final」礼物交换

标签: 传统 | 时间限制: 2500 ms | 内存限制: 1024 MiB |

题目描述

题目译自 JOI 2024 Final T4 「プレゼント交換 / 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, \ldots, R_{j}$ 组成。

对于一个由 $2$ 人以上的学生组成的组合，如果他们可以在组内互换礼物，而不会有人收到自己带来的礼物或者不满意的礼物，那么这个组合就是可行的。准确地说，由 $m$ 名 $(m \geq 2)$ 学生 $p_{1}, p_{2}, \ldots, p_{m}$ 组成的组合是可行的，当且仅当存在一个由 $p_{1}, p_{2}, \ldots, p_{m}$ 重新排列得到的数列 $q_{1}, q_{2}, \ldots, q_{m}$，这里 $q_{k}\ (1 \leq k \leq m)$ 表示给学生 $p_{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 想要让礼物交换会成功的，所以他想要知道这 $Q$ 个组合中，哪些是可行的。

给定学生的信息和组合的信息，对于每个组合，判断它是否是可行的，并编写一个程序来输出结果。

输入格式

第一行包含一个整数 $N$。

第二行包含 $N$ 个用空格分隔的整数 $A_1,A_2,\ldots ,A_N$。

第三行包含 $N$ 个用空格分隔的整数 $B_1,B_2,\ldots ,B_N$。

第四行包含一个整数 $Q$。

接下来的 $Q$ 行，每行包含两个整数 $L_i,R_i$。

输出格式

输出 $Q$ 行。第 $j\ (1 \leq j \leq Q)$ 行如果第 $j$ 个组合是可行的输出 Yes，否则输出 No。

样例 1

输入

4
3 8 5 7
2 6 1 4
3
3 4
1 3
1 4

输出

Yes
No
Yes

第一个组合是由 $2$ 名学生 $3,4$ 组成的。如果学生 $3$ 收到学生 $4$ 的礼物，学生 $4$ 收到学生 $3$ 的礼物，那么由于 $A_{3} \geq B_{4}$ 且 $A_{4} \geq B_{3}$ ，所以两个学生都不会不满。因此，这个组合是可行的，所以在第一行输出 Yes。

第二个组合是由 $3$ 名学生 $1,2,3$ 组成的。由于 $A_{1}<B_{2}$ 且 $A_{3}<B_{2}$ ，所以学生 2 不管收到学生 $1$ 还是学生 $3$ 的礼物，都会感到不满。因此，这个组合不是可行的，所以在第二行输出 No。

第三个组合是由 $4$ 名学生 $1,2,3,4$ 组成的。例如，如果学生 $1$ 收到学生 $2$ 的礼物，学生 $2$ 收到学生 $4$ 的礼物，学生 $3$ 收到学生 $1$ 的礼物，学生 $4$ 收到学生 $3$ 的礼物，那么没有人会不满。因此，这个组合是可行的，所以在第三行输出 Yes。这个样例满足子任务 $1,2,4,7,8$ 的限制。

这个样例满足子任务 $1,2,4,7,8$ 的限制。

样例 2

输入

3
5 6 3
1 4 2
1
1 3

输出

Yes

这个样例满足子任务 $1,2,3,4,7,8$ 的限制。

样例 3

输入

5
3 4 6 9 10
1 2 5 7 8
3
1 5
1 2
2 4

输出

No
Yes
No

这个样例满足子任务 $1,2,4,5,6,7,8$ 的限制。

样例 4

输入

10
2 5 8 10 12 14 16 17 19 20
1 4 7 6 11 13 9 3 18 15
8
2 9
1 6
2 8
2 4
1 2
1 6
7 10
5 8

输出

No
No
Yes
No
No
No
Yes
Yes

这个样例满足子任务 $1,2,4,6,7,8$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 5\times 10^5$
• $1 \leq B_{i}<A_{i} \leq 2N\ (1 \leq i \leq N)$
• $A_{1}, B_{1}, A_{2}, B_{2}, \ldots, A_{N}, B_{N}$ 各不相同
• $1 \leq Q \leq 2\times 10^5$
• $1 \leq L_{j}<R_{j} \leq N\ (1 \leq j \leq Q)$

详细子任务附加限制及分值如下表所示。

子任务	附加限制	分值
$1$	$N \leq 10, Q \leq 10$	$4$
$2$	$N \leq 18, Q \leq 10$	$5$
$3$	$N \leq 10^5, A_{1} \geq 2 N-2, B_{1}=1, Q=1, L_{1}=1, R_{1}=N$	$10$
$4$	$N \leq 10^5, Q \leq 10$	$31$
$5$	$N \leq 10^5, A_{i}<A_{i+1}, B_{i}<B_{i+1}\ (1 \leq i \leq N-1)$	$8$
$6$	$N \leq 10^5, A_{i}<A_{i+1}\ (1 \leq i \leq N-1)$	$12$
$7$	$N \leq 10^5$	$18$
$8$	无附加限制	$12$