#P9420. [JOI 2024 Final]礼物交换

    ID: 5758 传统题 3500ms 1024MiB 尝试: 5 已通过: 5 难度: 8 上传者: 标签>CF2500提高+/省选-二分图建模Hall 定理懒标记线段树普通线段树离线查询查询排序

[JOI 2024 Final]礼物交换

题目描述

JOI 学园有 NN 名学生,每个学生都有一个从 11 到 NN 的编号。

JOI 学园计划近期举办一个礼物交换会。每个学生都要准备一份礼物带到会场,学生 i (1≤i≤N)i\ (1 \leq i \leq N) 带来的礼物的价值是 AiA_{i} 。学生们都不喜欢收到比自己带来的礼物价值低很多的礼物,具体来说,学生 ii 如果收到价值低于 BiB_{i} 的礼物,就会感到不满。保证 Bi<AiB_{i}<A_{i}。

不过,并不是所有 NN 名学生都会真的参加礼物交换会。JOI 学园的校长 K 正在考虑 QQ 种可能参加礼物交换会的学生组合,第 j (1≤j≤Q)j\ (1 \leq j \leq Q) 种组合由 Rj−Lj+1R_{j}-L_{j}+1 名学生 Lj,Lj+1,…,RjL_{j}, L_{j}+1, \ldots, R_{j} 组成。

对于一个由 22 人以上的学生组成的组合,如果他们可以在组内互换礼物,而不会有人收到自己带来的礼物或者不满意的礼物,那么这个组合就是可行的。准确地说,由 mm 名 (m≥2)(m \geq 2) 学生 p1,p2,…,pmp_{1}, p_{2}, \ldots, p_{m} 组成的组合是可行的,当且仅当存在一个由 p1,p2,…,pmp_{1}, p_{2}, \ldots, p_{m} 重新排列得到的数列 q1,q2,…,qmq_{1}, q_{2}, \ldots, q_{m},这里 qk (1≤k≤m)q_{k}\ (1 \leq k \leq m) 表示给学生 pkp_{k} 送礼物的学生的编号,满足以下的条件:

  • 对于所有的 k (1≤k≤m)k\ (1 \leq k \leq m) ,pk≠qkp_{k} \neq q_{k}。
  • 对于所有的 k (1≤k≤m)k\ (1 \leq k \leq m) ,Aqk≥BpkA_{q_{k}} \geq B_{p_{k}}。

校长 K 想要让礼物交换会成功的,所以他想要知道这 QQ 个组合中,哪些是可行的。

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

输入格式

第一行包含一个整数 NN。

第二行包含 NN 个用空格分隔的整数 A1,A2,…,ANA_1,A_2,\ldots ,A_N。

第三行包含 NN 个用空格分隔的整数 B1,B2,…,BNB_1,B_2,\ldots ,B_N。

第四行包含一个整数 QQ。

接下来的 QQ 行,每行包含两个整数 Li,RiL_i,R_i。

输出格式

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

4
3 8 5 7
2 6 1 4
3
3 4
1 3
1 4
Yes
No
Yes
3
5 6 3
1 4 2
1
1 3
Yes
5
3 4 6 9 10
1 2 5 7 8
3
1 5
1 2
2 4
No
Yes
No
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

数据范围与提示

对于所有输入数据,满足:

  • 2≤N≤5×1052 \leq N \leq 5\times 10^5
  • 1≤Bi<Ai≤2N (1≤i≤N)1 \leq B_{i}<A_{i} \leq 2N\ (1 \leq i \leq N)
  • A1,B1,A2,B2,…,AN,BNA_{1}, B_{1}, A_{2}, B_{2}, \ldots, A_{N}, B_{N} 各不相同
  • 1≤Q≤2×1051 \leq Q \leq 2\times 10^5
  • 1≤Lj<Rj≤N (1≤j≤Q)1 \leq L_{j}<R_{j} \leq N\ (1 \leq j \leq Q)

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

子任务 附加限制 分值
11 N≤10,Q≤10N \leq 10, Q \leq 10 44
22 N≤18,Q≤10N \leq 18, Q \leq 10 55
33 $N \leq 10^5, A_{1} \geq 2 N-2, B_{1}=1, Q=1, L_{1}=1, R_{1}=N$ 1010
44 N≤105,Q≤10N \leq 10^5, Q \leq 10 3131
55 $N \leq 10^5, A_{i}<A_{i+1}, B_{i}<B_{i+1}\ (1 \leq i \leq N-1)$ 88
66 N≤105,Ai<Ai+1 (1≤i≤N−1)N \leq 10^5, A_{i}<A_{i+1}\ (1 \leq i \leq N-1) 1212
77 N≤105N \leq 10^5 1818
88 无附加限制 1212