C - Sort Subarray Editorial by Tamiji


\(A_i,\dots,A_{i+K-1}\) をソートしたとき, \(A_i\le\cdots\le A_{i+K-1}\) が満たされることから, \(A\) 全体が広義単調増加になるには以下の条件を満たしていればよいです.

  • \(A_1\le\cdots\le A_{i-1}\)
  • \(i\ge 2\) のとき,変更後の \(A\) に対し \(A_{i-1}\le A_i\) .すなわち,元の \(A\) に対し \(A_{i-1}\le\min_{i\le j< i+K}A_j\)
  • \(i+K\le N\) のとき,変更後の \(A\) に対し \(A_{i+K-1}\le A_{i+K}\) .すなわち,元の \(A\) に対し \(\max_{i\le j< i+K}A_j\le A_{i+K}\)
  • \(A_{i+K}\le\cdots\le A_N\)

このとき, \(1,4\) つ目の条件が成立するかは,前・後ろから順に見ることで確かめられます.また, \(2,3\) つ目の条件は Segment Tree またはスライド最小値・最大値を使って確かめられます.

計算量は \(O(N\log N)\) もしくは \(O(N)\) です.