2/4 日記
眠すぎる
応用情報、勉強する時間があるのか謎。。。
解説ACした。Q回のswapで増加する転倒数は最大でQであり、ソートクエリのときは合計高々Q回のswapを行うことにより計算量が抑えられるというもの。
A[x]>A[x+1] を満たすxをsetで管理すれば、ソートクエリのときに二分探索でa <= x <= bとなるような最小のxを求めることができ、間に合う。
実装がやや重かった。
aの値が1か2なので、1列目と2列目をなんらかのデータ構造（データの削除、追加、検索、最大値の取得が高速にできるもの）で保持すればよい。自分はpriority_queue+Tの値を座圧して配列に情報を保持、でやったけど、setでやったほうが実装がやや軽くなるみたい。明日実装しようかな。
最終問題にしてはそこまで難しくなかった。
dp[i]:=i番目まで見たときのY-Xの最大値
というdpはすぐに思いつく。普通に更新するとO(NM)かかる。
ここで、j番目の鍵屋はl j ~ r jまでをcost jで開錠できるという情報を、イベントソートする要領で処理したくなる（イベントの追加と削除ができればdpの更新は簡単）。
イベントを追加するとき、イベントの位置をposとすると、posまでの宝箱をすべて開けたときに得られる合計金額をnowとする。すると、setに(dp[pos-1]-now-cost)を追加すれば、位置iに来た時にsetの最大値をMXとして
now+MXが答えとなることが分かる。
ねんねぽよ
