AGC超楽しい！
概要
長いので省略
考察(部分点)
とりあえず「数$i$が何個あるか？」を考える。次に全消し可能な条件を考えると、数$i$を消した時に残るボールの個数が常にその時点の最大値に一致していればよいことがわかる。例えば$[1,3,3,5,5]$だと5を消した時に$[1,3,3]$となり、さらに3を消せば$[1]$となるのでよい。しかし$[1,1,3,5,5]$だと$[1,1]$で止まってしまう。また、$[1,2,3,4,4]$はそもそもボールが消えない。
全消し可能条件から攻める。全ての$r$について、「($r$の書かれたボールがある場合) $r$以上の数を消した後何個残るか」を計算する。そして、この状態を一次元にプロットする。具体的には、$r$以上の値を除いた結果が$l$だとすると、$[l+1,r]$に1を加算する。(これ以降それぞれを「区間」と呼ぶ)
図は上から順に$[1,3,3,4,5] , [1,2,2,5,5] , [1,1,1,4,4]$である。ひとつわかることとして、上で定めた区間の集合が$[1,n]$全体を覆うことと全消し可能なことは同値である。(意味的に考えるとわかる)
また、区間の集合が$[1,n]$を覆っていない場合は全消し不可能であることもわかる。(あるタイミングで残り個数と始点が一致しなくなるため)
あと考えなければならないことは、全消し可能な列に変化させるために必要な操作回数である。パッと見た感じでは$([1,n]から外れている個数)+(max(kを覆っている区間の数-1,0) )$が答えになりそうで、実はこれが達成できる。 区間に施せる操作が左端を詰めることだけである(=ある数が書かれたボールを一時的に削除する)ことに注意して、これは以下のようにして達成できる。
2番目の操作で重なりを1つ減らせる理由は2つの区間の重なり方を何通りか試すことでわかる。これを各クエリに対して愚直に実装することによって、部分点の500点を得ることができる。
考察(満点)
各クエリで行われることはある数字が消えて別の数字が書かれるだけなので、変化が起きる区間の数は高々2個である。
まず変化前と変化後で数字が変わらない場合、答えも変わらないのでそのようなケースは除外する。
変化前の数を$X$, 変化後を$Y$とおく。このとき、$X$についての区間の左端が1縮んで$Y$についての区間の左端は1伸びる。区間が完全に消滅する場合や新しく誕生する場合などに気を付けて実装を行うことで、満点を得られる。
所感
なんでこれ本番35人しか解いてないんだろう 個人的にはGame on Treeより簡単に見える
