#P13297. 相似数组判断

    ID: 12481 传统题 文件IO:similarity 2000ms 256MiB 尝试: 17 已通过: 6 难度: 9 上传者: 标签>CF2700省选/NOI-笛卡尔树单调栈二分图建模排序贪心交换论证增广路有序集合区间合并CF1718D

相似数组判断

我们称一个数组 纯(pure),如果其中所有元素两两不同。
例如,[1,7,9][1,7,9] 是纯的,[1,3,3,7][1,3,3,7] 不是纯的(因为元素 33 出现了两次)。

两个纯数组 b,cb,c 相似(similar) 当且仅当它们长度相同(记为 nn),并且对所有下标对 (l,r)(l,r) 满足 1≤l≤r≤n1\le l\le r\le n,都有

$$\operatorname{argmax}\big([\,b_l,b_{l+1},\dots,b_r\,]\big) = \operatorname{argmax}\big([\,c_l,c_{l+1},\dots,c_r\,]\big),$$

其中 argmax⁡(x)\operatorname{argmax}(x) 表示序列 xx 中 最大元素的下标(对纯数组该下标唯一)。
例如,$\operatorname{argmax}([3,4,2])=2,\ \operatorname{argmax}([1337,179,57])=1$。


Tonya 得知 Burenka 喜欢一个长度为 nn 的排列 pp(pp 是 [1..n][1..n] 的一个排列)。他想送她一个与 pp 相似 的数组 aa。目前 aa 中有一些元素已被固定,但恰好有 kk 个位置为空(这些位置暂时令 ai=0a_i=0),并且保证 k≥2k\ge 2。另有一个集合 SS,包含 k−1k-1 个两两不同的数字。

Tonya 发现自己还缺最后 一个数字用于填满 aa 中的空位,所以他打算购买这个数。他有 qq 个可选的购买数字 dd。Tonya 认为一个数 dd 是合适的,当且仅当存在一种方式,用 SS 中的 k−1k-1 个数 和 该数字 dd 去替换 aa 中所有的 00,使得

  1. 最终得到的 aa 是纯数组(元素两两不同),且
  2. 最终的 aa 与排列 pp 相似。

对每个候选的 dd,判断它是否合适。


输入格式

首行一个整数 tt,表示测试组数,满足

1≤t≤104.1\le t\le 10^4.

对每组测试:

  • 第一行两个整数 n,qn,q,满足

    $$1\le n\le 3\times 10^5,\quad 1\le q\le 3\times 10^5.$$
  • 第二行给出排列 p1,p2,…,pnp_1,p_2,\dots,p_n,满足

    $$p\text{ 是 }[1..n]\text{ 的排列} \ \Longleftrightarrow\ 1\le p_i\le n\ \text{且 }p_i\text{ 两两不同}.$$
  • 第三行给出数组 a1,a2,…,ana_1,a_2,\dots,a_n,满足

    $$0\le a_i\le 2\times 10^9,\quad \exists\, i\ne j:\ a_i=a_j=0$$

    (即空位数 k≥2k\ge 2)。

  • 第四行给出 k−1k-1 个互不相同的整数 s1,…,sk−1s_1,\dots,s_{k-1},满足

    1≤si≤2×109,si 两两不同.1\le s_i\le 2\times 10^9,\quad s_i\text{ 两两不同}.
  • 接下来 qq 行,每行一个整数 dd,满足

    1≤d≤2×109.1\le d\le 2\times 10^9.

保证条件: 对于每个给定的 dd,总可以用 S∪{d}S\cup\{d\} 中的 kk 个互异数字填满 aa 的 kk 个空位(即能使结果成为纯数组)。
全局约束: 所有测试中 ∑n≤3×105\sum n\le 3\times 10^5 且 ∑q≤3×105\sum q\le 3\times 10^5。


输出格式

对每个测试的每个查询 dd,若存在一种填充方式使最终 aa 为纯数组且与 pp 相似,则输出 YES 否则输出 NO。


样例

4
4 3
1 4 3 2
5 0 7 0
6
9
1
4
5 3
1 2 5 4 3
0 5 10 0 0
3 9
1
8
11
5 2
1 4 3 2 5
0 0 0 0 0
7 9 1 5
6
100
4 2
4 1 3 2
0 5 3 0
2
4
6
YES
NO
NO
YES
YES
NO
YES
YES
NO
NO

说明:

  • 样例 1 的第一组:若取 d=9d=9,可得到 a=[5,9,7,6]a=[5,9,7,6],可以证明该 aa 与 pp 相似;而 d=1d=1、d=4d=4 时无解。
  • 样例 2 的第二组:d=1d=1 时可得 a=[1,5,10,9,3]a=[1,5,10,9,3];d=8d=8 时可得 a=[3,5,10,9,8]a=[3,5,10,9,8];d=11d=11 时不可行。

子任务

子任务 附加限制 分值
1 n,q≤50n,q\le 50 10
2 空位数 恰为 k=2k=2;其它与总约束一致。 20
3 只有一个查询(q=1q=1)。 30
4 满约束:∑n,∑q≤3⋅105\sum n,\sum q\le 3\cdot 10^5,多次查询。 40

大数据