← 返回题目列表

AtCoder · joi2024ho_d

D. 礼物交换

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

配点: 100 点

問題文

JOI学校 有 N 名学生,每个学生都有 它们的编号最大为 1 假设一直下雨,直到 N 。

JOI学院计划近期举办礼物交换活动。 每个学生都有一份礼物可以带到那里。 1 每个学生都被提供 i (1\leqq i \leqq N) 计划带来的礼物的价值是 A_i 。 学生不喜欢收到与自己带来的礼物相比价值太低的礼物; i 是一个值 当我收到价值低于 B_i 的礼物时,我会感到不满意。 在这里,B_i < A_i 成立。

但是,N 并非所有学生都真正参加礼物交换活动。 JOI学院院长K主席作为参加礼物交换活动的学生们发表了讲话。 Q 可能性, 组j 個目 (1\leqq j\leqq Q) 是 R_j-L_j+1 学生 它由 L_j,L_j+1,\dots,R_j 组成。

是 2 对于一个以上学生组成的团体,如果一个人可以在团体内交换礼物而没有收到或对他们带来的礼物不满意,则该团体是可以兑换礼物 据说。 严格来说,m 人 (m \geqq 2)学生 由 p_1,p_2,\dots,p_m 组成的组可以兑换礼物 据说意味着 通过重新排列p_1,p_2,\dots,p_m 创建的编号规则 q_1,q_2,\dots,q_m 表示存在满足以下两个条件的东西。 此外,q_k (1\leqq k\leqq m) 是一名学生 它代表将礼物送给 p_k 的学生人数。

  • 全部 k (1\leqq k\leqq m),p_k \neq q_k.
  • 全部 k (1\leqq k\leqq m),A_{q_k} \geqq B_{p_k}.

K主席希望礼物交换活动取得成功。 我们正在尝试了解每个Q 组是否可以交换礼物。

给定学生信息和小组信息,创建一个程序来确定是否可以为每个小组交换礼物。


入力

输入是按以下格式从标准输入给出的。

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 \leqq j \leqq Q)有j 如果第h组可以交换礼物 Yes ,否则 No 。 如果有多个答案与


制約

  • 2 \leqq N \leqq 500\,000.
  • 1 \leqq B_i < A_i \leqq 2N (1\leqq i\leqq N).
  • A_1,B_1,A_2,B_2,\dots,A_N,B_N 都是不同的。
  • 1 \leqq Q \leqq 200\,000.
  • 1 \leqq L_j < R_j \leqq N (1\leqq j\leqq Q).
  • 所有输入值都是整数。 第

小課題

  1. (4 点) N \leqq 10,Q \leqq 10.
  2. (5 点) N \leqq 18,Q \leqq 10.
  3. (10 点) N \leqq 100\,000,A_1 \geqq 2N-2,B_1=1,Q=1,L_1=1,R_1=N.
  4. (31 点) N \leqq 100\,000,Q \leqq 10.
  5. (8 点) N \leqq 100\,000,A_i < A_{i+1},B_i < B_{i+1} (1\leqq i\leqq N-1).
  6. (12 点) N \leqq 100\,000,A_i < A_{i+1} (1\leqq i\leqq N-1).
  7. (18 点) N \leqq 100\,000.
  8. (12 点)没有额外的限制。

入力例 1

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

出力例 1

Yes
No
Yes

1 组是 它由2 学生 它由 3,4 组成。 学生 3 是一名学生 4 给学生的礼物 如果您收到 4 是一名学生 3 的礼物,A_3\geqq B_4 和 A_4\geqq B_3 两个学生都不满意。 所以,既然这个团体可以交换礼物,1 在线 来自 Yes 。 在

2 组是 它由3 学生 它由 1,2,3 组成。 A_1 < B_2 和 A_3 < B_2 ,学生 2 是一名学生 1,3 无论收到什么礼物,我最终都会感到不满意。 因此,这个团体不能交换礼物,所以 它由2 在线 来自 No 。 在

3 组是 它由4 学生 它由 1,2,3,4 组成。 例如,学生 没有人会因为收到一份 1 是一名学生 2 给学生的礼物 如果您收到 2 是一名学生 4 给学生的礼物 如果您收到 3 是一名学生 1 给学生的礼物 如果您收到 4 是一名学生 3 礼物而感到不满意。 所以,既然这个团体可以交换礼物,3 在线 来自 Yes 。 在

此输入示例是一个小作业。 1,2,4,7,8 满足约束。


入力例 2

3
5 6 3
1 4 2
1
1 3

出力例 2

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

出力例 3

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

出力例 4

No
No
Yes
No
No
No
Yes
Yes

此输入示例是一个小作业。 1,2,4,6,7,8 满足约束。