#P18594. Permutation Compression
Permutation Compression
Permutation Compression
给定一个长度为 的排列 。你有 件工具,第 件工具对应一个整数 ,每件工具至多使用一次。
使用一件工具时,在当前序列中选择一个长度恰为 的连续区间,并删除这个区间中最大的元素。其余元素保持相对顺序,删除后序列长度减少1。可以不使用某些工具。
现在给定一个长度为 的目标序列 ,其中的元素互不相同,且都在 到 之间。判断能否经过若干次上述操作,把 变为 。
输入格式
第一行给出测试组数 。每组测试包含四行:
第一行给出三个整数 。
第二行给出 个整数 ,构成 到 的一个排列。
第三行给出 个互不相同的整数 ,均在 到 之间。
第四行给出 个整数 。
数据满足:
- ;
- ,;
- ;
- 所有测试组的 之和不超过 ;
- 所有测试组的 之和不超过 。
目标序列不保证是原排列的子序列;工具长度可以重复。
输出格式
每组测试输出一行:能够得到目标序列时输出 YES,否则输出 NO。
样例输入 1
3
5 2 3
5 1 3 2 4
5 2
1 2 4
5 5 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
3 2 2
3 1 2
3 2
2 3
样例输出 1
YES
YES
NO