C - Range Flip
Editorial
/
Time Limit: 2 sec / Memory Limit: 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
どのように操作しても一致させることができません。