AtCoder Grand Contest 017 C 「Snuke and Spells」

問題文

C - Snuke and Spells

 

整数iの書かれたボールの個数をcnt[i]と表す。

i個のボールがあるとき、魔法を唱えるとボールはi-cnt[i]個になる。ここで各整数iについて[i-cnt[i],i]という区間があるとすると、「魔法を唱えることでボールを0個に出来る」ということと「これらの区間で、区間[0,N]が完全に覆われる」ということが同値だということがわかる。

何故なら、区間の長さの和はNなので、[0,N]を完全に覆うためにははみ出している区間や重なっている区間があってはダメで、それがないときは魔法を唱えるたびに最大値を消していけるから。

Snukeくんは「整数Xの書かれたボールを整数Yの書かれたボールにする」という操作が出来るが、これは[X-cnt[X],X]を[X-cnt[X]+1,X]に縮めて、[Y-cnt[Y],Y]を[Y-cnt[Y]+1,Y]に伸ばすことに対応する。1回の操作で増やせる覆われた所の長さは高々1なので、元々覆われていない所の長さがLだとするとすくなくともL回の操作が必要。

そして、重なっている所やはみ出している所を縮めて覆われていない所を伸ばすことで、ちょうどL回の操作で目的を達成できるから、これが最小回数だということがわかる。

よってクエリが来るごとに「覆われていない所の長さ」を更新していけばよい。