ABC260 精進メモ - こゃーその雑記

問題

思考過程

長ければ長いほど、とりあえず条件は満たせるので、どこまで「短くできるか」ということを考える。となると、おそらく各区間の端っこの部分で、ここでどうなるかを考える。

最初に、区間の「 $A_i$ の最大値」と「 $B_i$ の最小値」を考えてみる。が、いまいちピンとこない（入力例1だとなにか言えそうだが、入力例3だとよくわからない）。「 $A_i$ の最大値」と「 $B_i$ の最小値」のどちらが大きいかは入力によりそうなので、この値からなにかいうのは難しそう。

では端からどちらか選んでみることを考えてみるとどうか？
入力例3の1つ目(と2つ目)の区間で "1" を選ぶとする。すると、どこまで長くしなければいいか考えてみると、「1よりも大きい中で最大の区間の端のどちらか」である。この場合は "5" になる。ということで、"1"始まりの良い数列の長さは、長さが5から9まで1つづつある。

つぎに、5つ目の区間で "2"を選ぶ、つまり始まりを"2"にすることを考えると、2つ目の区間では"1"が選ばれなかったため、 "7"を選ぶ必要がある。つまり、最低でも"7"以上まで伸ばす必要がある。

こう考えていくと、「良い数列の左端を固定したとき、選ぶ必要のある数の中での最大値が、右端になりうる最小値」として考えられる。ある区間については、最初は $A_i$ が選ばれる候補であるが、良い数列の左端の数字が $A_i$ を超えてしまった場合は $B_i$ が候補になる。最小の $B_i$ よりの大きい数が左端の数字になったら打ち切る。

ということで、候補の数は最大で $N$ 個で、入れ替えが生じるものに対して最大値が取れればいいので、sorted_setを使えば高速で判定が可能になる。Pythonであれば、tatyamさんのSortedSetを使って、追加・削除で $O(\sqrt{N})$ 、最大値の取得に $O(\log{N})$ でできるので、全体として計算量は $O(N\sqrt{N} + M\log{N})$ でできる。
あと、作れる長さを範囲で足し算するのは、imos法*1を使うことで $O(N)$ でできる。

ACコード

atcoder.jp

*1:厳密にはimos法とは言わないという話を聞いたような気がする（うろ覚え）