AtCoder Grand Contest 038 B - Sorting a Segment

公式解説と少し違う方法で解いたので記録。

解法

ある長さ $K$ の区間を昇順に並び替えた時に、値が変更される最左のインデックスを $l$ 、最右のインデックスを $r$ とします。この時操作の結果は、閉区間 $\lbrack l, r \rbrack$ 内の要素を昇順に並び替えたものとなります。つまりこの区間 $\lbrack l, r \rbrack$ は「操作によって実質的に並び替えられたのはどの区間か」というものを表します。

f:id:betrue12:20190922003715p:plain

求めたい答えは、 $N-K+1$ 通りの全ての操作パターンについてこのようなインデックスの組 $\lbrace l, r \rbrace$ を求めた時の、それらの相異なる要素数となります。ただし1つも要素が変更されない場合もあるので、その場合は適当に $\lbrace l, r \rbrace = \lbrace -1, -1 \rbrace$ などとしておきます。（開区間と紛らわしいので値の組は $\lbrace \cdot, \cdot \rbrace$ と表記します）

では各操作パターンについて、長さ $K$ の区間 $\lbrack i, i+K-1\rbrack$ を操作したときの $l, r$ はどのように求めれば良いでしょうか。左右同様の方法で求められるので $l$ について考えます。

左端から見て、要素が変更されていない区間 $\lbrack i, l-1\rbrack$ に注目します。この区間に属する全ての値 $j\in \lbrack i, l-1\rbrack$ が満たすべき条件は、 $P_{j}$ より小さい要素が区間 $\lbrack j, i+K-1\rbrack$ に存在しないことです。