#P18788. [KOI2026 二轮] 数列操作

[KOI2026 二轮] 数列操作

[KOI2026 二轮] 数列操作(수열 연산 / Sequence Operations)

题目描述

给定长度为 NN 的排列 AA 和长度为 MM 的数列 BB。AA 包含 11 到 NN 各一次;BB 的元素互不相同,均在 11 到 NN 之间。

初始令数列 X=AX=A。可以对 XX 进行零次或多次以下操作。若当前长度为 KK:

  • 交换:选择 1≤i<K1\le i<K,且满足 Xi<Xi+1X_i<X_{i+1},交换这两个相邻元素。
  • 合并:选择 1≤i<K1\le i<K,把相邻的 Xi,Xi+1X_i,X_{i+1} 替换为一个数 min⁡(Xi,Xi+1)\min(X_i,X_{i+1}),使数列长度减少 11。

判断能否使 XX 与 BB 完全相同。若能,输出任意一个操作序列,操作数不超过 N2N^2。无需最小化操作次数。可以证明,只要可以变成 BB,就存在满足该操作次数上限的方案。

输入格式

第一行两个整数 N,MN,M。

第二行 NN 个整数 A1,…,ANA_1,\ldots,A_N。

第三行 MM 个整数 B1,…,BMB_1,\ldots,B_M。

输出格式

若无解,输出一行 NO。

若有解,第一行输出 YES,第二行输出操作数 QQ(0≤Q≤N20\le Q\le N^2),接下来 QQ 行按执行顺序输出操作:

  • 1 i:交换当前的第 i,i+1i,i+1 个元素,执行前必须满足 Xi<Xi+1X_i<X_{i+1};
  • 2 i:合并当前的第 i,i+1i,i+1 个元素,保留较小值。

每个位置编号均针对该操作执行前的当前数列,从 11 开始。所有操作的位置必须有效,最终数列必须精确等于 BB。多种合法方案都可接受。

样例 1

4 2
1 4 2 3
3 1
YES
6
1 1
1 2
1 3
2 1
1 1
2 2

数列依次变为 $[4,1,2,3]\to[4,2,1,3]\to[4,2,3,1]\to[2,3,1]\to[3,2,1]\to[3,1]$。

样例 2

2 1
1 2
2
NO

样例 3

4 4
3 2 1 4
3 1 2 4
NO

样例 4

4 2
1 3 2 4
1 3
NO

数据范围与子任务

所有输入均为整数,1≤M≤N≤30001\le M\le N\le3000。AA 是 1,…,N1,\ldots,N 的排列,BB 的元素互不相同且属于 [1,N][1,N]。

子任务 分值 附加限制
1 7 N≤8N\le8
2 8 M=1M=1
3 12 M=NM=N
4 10 所有 Ai=iA_i=i
5 13 M=N−1M=N-1
6 15 BB 是 AA 的子序列
7 30 N≤300N\le300
8 5 无附加限制

满分 100 分。时限 2 秒,内存 1024 MiB。使用 SPJ 验证方案。