Codeforces #332 Div2 C. Day at the Beach

※このエントリは競プロで圧倒的成長 Advent Calendar 2015の4日目のエントリです．

なんと日本時間で間に合っている．

問題はこちら

本番では疲れからかB問題でWA生やしまくって問題を読むに至らなかった．

問題要約

• n個の数字が与えられ，昇順にソートする
• ソートの方法として，「そのブロックさえソートすれば全体のソートが完了する」というブロックに分けてからソートをする
• できるだけ小さいブロックに分けた時，ブロックはいくつになるか

解法

• 左から貪欲にブロックを求めていく
• 現在着目している範囲内にある数字の最大値が，それより右側にある数字の最小値以下ならブロック化してもよい
• 最大値，最小値ともに，セグメントツリーで求めることができる

セグメントツリーは蟻本にのっているものとほぼ変わらないので割愛．
持ってない人は買おう！