C - Range Flip 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

問題文

長さ 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

どのように操作しても一致させることができません。