yukicoder No.1734 Decreasing Elements 解説
$ A_x=A_y\ (x<y) が成り立つとき、$ j<x までの操作で $ A_x=A_y=0 となるか、$ j=xでの操作で $ A_y=0 となるため、 $ j=y として操作を行うことはないことがわかります。よって操作を行うごとに各値 $ n に対する $ A_i=n となる $ i の最小値 $ pos_iを更新しながら管理し、$ j=x として操作を行うことがあるかを求めることでこの問題は解けます。
現在の $ A_i の最大値が $ M であり、操作を $ K=n として行う場合、$ pos_i \leftarrow \min(pos_i,\ pos_{i+n})\ (1 \le i \le M-n) という更新を行うことになりますが、これは配列を適切に利用することで $ n \le M-n のとき $ O(n) 、$ M-n <n のとき $ O(M-n) で行うことができ、最大値はそれぞれ $ M-n,\ n 以下の値に更新されます。
操作 $ 1 回あたりの計算量が最大値の変化量の定数倍で抑えられていることを考えると上記の更新を最後まで愚直に行っても計算量は $ O(A_{max}) になることがわかります。