← 返回题目列表

AtCoder · utpc2020_c

C. 范围翻转

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

問題文

长度 小于或等于 N 整数序列 给出 A_1, \ldots, A_N 和 按字典顺序比较 1 以上 N 的正整数 给出了 D 被给予。考虑重复以下操作。

  • 1 \leq L \leq R \leq N 和 R-L+1=D 一个整数使得 L , R 和整数 X ,A_L, A_{L+1}, \ldots ,A_R 一起,(X-A_L), (X-A_{L+1}), \ldots, (X-A_R) 改写为。

A_1, A_2, \ldots, A_N 在有限次操作中 B_1, B_2, \ldots, B_N 一致,如果可能,在操作步骤中满足以下所有条件的操作次数为 1 请配置一个。

  • 次,也可以为 3\times 10^5 回以下。( 0 次。) 每次操作中
  • 的绝对值为 X ,为 10^{13} 以下。
。此外,在本问题的限制下,如果可以通过有限次操作使其一致,则可以证明存在满足上述所有条件的操作步骤。 如果可以使其一致,则为

制約

  • 所有输入均为整数。
  • 1 \leq D \leq N \leq 3\times 10^5
  • \lvert A_i \rvert \leq 10^6
  • \lvert B_i \rvert \leq 10^6

部分点

  • 1 \leq N \leq 3\times 10^4 的数据集 给出 50 点。 如果您正确回答了所有满足

入力

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

N D
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N

出力

如果能够使其一致的话 Yes ,否则 No 。 Yes 输出 2 行输出操作次数 K \ (0 \leq K \leq 3\times 10^5) , 在其下方以以下格式表示操作步骤 K 行。

L_1 R_1 X_1
\vdots
L_K R_K X_K

但是, 运算前设定中包含的L_i, R_i,X_i(1 \leq i \leq K)是 您也可以写 i 在第次操作中 L,R,X 的值。 如果满足条件的解有多个,输出任意一个即可。


入力例1

4 2
1 2 3 4
4 4 3 3

出力例1

Yes
3
1 2 5
3 4 7
2 3 7

  • 从初始状态(L,R,X)=(1,2,5)进行操作后 [1,2,3,4]\to [4,3,3,4] 。 对于
  • 下一步 砍掉(L,R,X)=(3,4,7)进行操作后 [4,3,3,4]\to [4,3,4,3] 。 对于
  • 最后(L,R,X)=(2,3,7)进行操作后[4,3,4,3]\to [4,4,3,3] 变为 通过 B 与之匹配。


入力例2

2 2
1 2
1 3

出力例2

No

无论如何操作都无法匹配。