魚2 (Fish2)
解説 nxteru (戸高空)問題概要
𝑁匹の魚が横一列に並んでいる
左から𝑖番目の魚の大きさは𝐴𝑖 である
𝑄個のクエリ𝑇𝑗 = 1

𝑋𝑗 番目の魚の大きさを𝑌𝑗 にする

𝑇𝑗 = 2

𝐿𝑗 から𝑅𝑗 番目までの魚を取りだして以下の問題を解く

問題概要
ある隣合う2匹の魚で大きい方が小さい方を食べて、食べた魚の大きさ分だけ大きくなるということが残り1匹になるまで繰り返される最後の1匹として残る可能性がある魚の数を求めよ
𝑁, 𝑄 ≤ 100000、魚の大きさ≤ 109

簡単な考察ある魚𝑠が残ることができるかを考える
このとき𝑠が隣り合う魚を食べる以外は考えなくてよい
また𝑠が隣り合う魚を食べられる場合は左右どちらでも食べてよい
よって「𝑠が隣り合う魚を食べられるなら食べる」を繰り返してすべての魚を食べられるかが分かればよい小課題１
𝑁, 𝑄 ≤ 500
すべての魚についてその魚が残ることができるかを調べる
各魚𝑂(𝑁)でシミュレーションできるのでクエリ当たり𝑂(𝑁 2 )で解ける
𝑂(𝑄𝑁 2 )小課題２
𝑄 = 1, 𝑇𝑗 = 2, 𝐿𝑗 = 1, 𝑅𝑗 = 𝑁
クエリが1回
シミュレーションを高速化する小課題２
右に向かってできるだけ食べることを考えると，今の大きさ以下の魚が連続していたら、その魚たちは大きさの加算分を計算しなくても食べられることが分かる
初めて計算が必要になるのは今の大きさより大きい魚が初めて現れる場所
そのような場所は例えばsegment tree上の二分探索で𝑂(𝑙𝑜𝑔𝑁)で求められる小課題２
そのような右に自分より大きな魚が初めてでてくる場所の手前まで食べてしまい，その合計だけ大きさの加算する

このように右に進めるだけ進む、左に進めるまで進むを繰り返してシミュレーションする
この左右に伸ばす回数はlog 2 max{𝐴}回で抑えられる
前の自分より大きな魚を食べると大きさが2倍以上になるためである
Ｏ（𝑁 log 𝐴 log 𝑁 ）考察
シミュレーションにおいて状態は[𝑙, 𝑟]…「𝑙～𝑟番目の魚を食べて今の大きさは𝐴𝑙 + 𝐴𝑙+1 + ⋯ + 𝐴𝑟 であり左隣が𝑙 − 1、右隣が𝑟 + 1である」というような区間であらわされる
クエリは[𝑖, 𝑖]からスタートして[𝐿, 𝑅]に到達できるような𝑖はいくつあるかを答える問題である

考察
ここで左にも右にも進めない状態、つまり𝐴𝑙 + 𝐴𝑙+1 + ⋯ + 𝐴𝑟 < 𝐴𝑟+1 かつ
𝐴𝑙 + 𝐴𝑙+1 + ⋯ + 𝐴𝑟 < 𝐴𝑙−1を満たす区間を閉塞区間とする

考察
実は「ある魚が区間[𝐿, 𝑅]に到達できる⇔その魚が[𝐿, 𝑅]の範囲のどの閉塞区間にも含まれていない」が成り立つ
閉塞区間[𝑙, 𝑟]に含まれている⇒魚𝑙 − 1,魚𝑟 + 1を食べることができない

閉塞区間に含まれていない⇒今の状態が閉塞区間でないなら必ず左右のどちらかに区間を伸ばせる．閉塞区間に到達することはないので、これを繰り返すと[𝐿, 𝑅]に到達できるイメージ（時間があれば追加する）
時間がありませんでした小課題３
この閉塞区間を求める
閉塞区間[𝑙, 𝑟]に関して
𝐴𝑙 , 𝐴𝑙+1 , … , 𝐴𝑟 < 𝐴𝑟+1
𝐴𝑙 , 𝐴𝑙+1 , … , 𝐴𝑟 < 𝐴𝑙−1が成り立つがこのような𝑙 − 1, 𝑟 + 1の組は𝑂(𝑁)個しかない小課題３
𝐴𝑙−1 < 𝐴𝑟+1 であるような組を考える
𝑙 − 1を固定したとき𝑟 + 1として考えられるのは𝐴𝑙−1 < 𝐴𝑥 を初めて満たす𝑥のみである
なぜなら𝑟 + 1がそのような𝑥より右側にいくと𝐴𝑥 を含んで
𝐴𝑙 , 𝐴𝑙+1 , … , 𝐴𝑟 < 𝐴𝑙−1 を満たさなくなる

l-1r+1

小課題３
同様に𝐴𝑙−1 ≥ 𝐴𝑟+1 であるような組についてもそれぞれの右端について左端の候補は1つである
これらの条件を満たす組はstackを用いて左から列を走査することで𝑂(𝑁)ですべて求めることができる小課題３
𝐴𝑖 を見るとき、stackのtopが𝐴𝑖 以下の間stackをpopし続ける
そして𝐴𝑖 をstackに入れる
このpopのときpopされる側にとって𝐴𝑖 が右側で初めて自分以上の場
所
𝐴𝑖 をstackに入れるときのstackのtopが𝑖にとって左側で初めて自分より大きくなる場所小課題３
クエリあたり𝑂(𝑁)で閉塞区間を求めて，それらの区間に含まれていない魚の数を求められる
𝑂(𝑄𝑁)閉塞区間についての考察
閉塞区間同士は交差せず内包するか重ならないかのどちらかである

右下のように[𝑎 + 1, 𝑏 − 1]と[𝑐 + 1, 𝑑 − 1]が交差したとすると𝑐が閉塞区間[𝑎 + 1, 𝑏 − 1]に含まれるので𝑐 < 𝑏𝑏が閉塞区間[𝑐 + 1, 𝑑 − 1]に含まれるので𝑏 < 𝑐で矛盾

bacd

小課題４
𝑇𝑗 = 2 （更新クエリがない）

最初に閉塞区間を求めておくと更新がないのでそれらを使うことができる小課題４
クエリ[𝐿, 𝑅]にこたえる

範囲[𝐿, 𝑅]のみを考えたとき𝐿 − 1に進めなくなるため，𝐿 − 1を左の壁とした新たな閉塞区間ができることがある
同様に𝑅 + 1を右の壁とした閉塞区間ができる小課題４
そのような𝐿 − 1を左の壁とする閉塞区間にどこまで含まれるか、つまり右の壁として条件を満たす一番右のものを求める
その条件は𝑠𝑢𝑚[𝑖]を𝐴1 + 𝐴2 + ⋯ + 𝐴𝑖−1 として𝑠𝑢𝑚[𝑥] − 𝑠𝑢𝑚[𝐿] < 𝐴𝑥 ⇔ −𝑠𝑢𝑚[𝐿] < 𝐴𝑥 − 𝑠𝑢𝑚[𝑥]である𝑥だから𝐴𝑥 − 𝑠𝑢𝑚[𝑥]の配列で−𝑠𝑢𝑚[𝐿]以上のもので𝑅以下もっとも右を求められればいい
Segment tree上の二分探索で𝑂(𝑙𝑜𝑔𝑁)小課題４
こうして新たにできた閉塞区間に含まれる左右の部分を除いた範囲をあらたに[𝐿, 𝑅]としてクエリにこたえる

すると[1, 𝑁]の範囲で求めた最初からある閉塞区間のみを考えて、[𝐿, 𝑅]の範囲でそれに含まれない場所の数を求める問題になる小課題４
もう一つのうれしい性質
この新たなクエリの区間と閉塞区間は交差せず、内包するか重ならないかのどちらかである
例えば図のように交差しているとすると、 𝐴𝑎+1 + ⋯ + 𝐴𝑏−1 は𝐴𝑎 以下だからクエリの𝑎 + 1以降の部分はさきほどの処理で除かれているはずである

a
クエリ

閉塞区間

b

小課題４
閉塞区間がクエリを含むか、クエリが閉塞区間を含むという関係

閉塞区間

クエリ

小課題４
閉塞区間がクエリを含むか、クエリが閉塞区間を含むという関係
クエリが含む閉塞区間のみを考えたときクエリの範囲でそれらに含まれない場所の数を求めたい

クエリ

小課題４
それぞれの場所がいくつの閉塞区間に含まれているかを考える

クエリ

2 4 4 3 4 2 3 4 3 21

小課題４
クエリが含む閉塞区間のみを考えたときそれらに含まれない場所⇔その場所が含む閉塞区間の数がクエリの範囲内で最小＝（クエリを丸ごと含む閉塞区間の数）

クエリ

2 4 4 3 4 2 3 4 3 2

小課題４
クエリは以下の問題に帰着
𝐵𝑖 …場所𝑖が含む閉塞区間の数の配列
クエリ[𝐿, 𝑅]
min{𝐵𝐿 , 𝐵𝐿+1 , … , 𝐵𝑅 } = 𝐵𝑖 を満たす𝑖の個数(𝐿 ≤ 𝑖 ≤ 𝑅)を求める小課題４
クエリ[𝐿, 𝑅]
min{𝐵𝐿 , 𝐵𝐿+1 , … , 𝐵𝑅 } = 𝐵𝑖 を満たす𝑖の個数(𝐿 ≤ 𝑖 ≤ 𝑅)を求める
これはsegment treeでできる小課題４
各ノードで持つ情報は最小値𝑚𝑖と最小値の個数𝑐𝑛𝑡
ノード𝐴とノード𝐵のマージは𝑚𝑖 = min(𝐴. 𝑚𝑖, 𝐵. 𝑚𝑖)，𝑐𝑛𝑡 = 0;
𝐼𝑓(𝑚𝑖 == 𝐴. 𝑚𝑖)𝑐𝑛𝑡 += 𝐴. 𝑐𝑛𝑡
𝐼𝑓(𝑚𝑖 == 𝐵. 𝑚𝑖)𝑐𝑛𝑡 += 𝐵. 𝑐𝑛𝑡

小課題５
小課題５は満点とやることはほとんど同じなので省略します
ただクエリが[1, 𝑁]のみなので満点と比べて簡単にできるたり省略できたりします

満点
更新あり
答えを求めるクエリは小課題4と同じようにする
そのために配列𝐵𝑖 …場所𝑖が含む閉塞区間の数を適切に更新する必要がある閉塞区間についての考察２
ある場所𝑥を含む閉塞区間の数は最大でlog 2 max{𝐴}個である（同様に区間の重なりの深さもlog 2 max{𝐴}個以下である）
右下のように重なっているとすると
𝑥 < min 𝑎, 𝑏𝑥 + 𝑏 > 2𝑥 < min 𝑎, 𝑐d𝑥 + 𝑏 + 𝑐(> 4𝑥) < min(𝑑, 𝑒)
左右の壁の下限が2倍になっていく

eaacxb

満点
場所𝑥を含む閉塞区間の数は𝑂(𝑙𝑜𝑔𝐴)個
値が更新されたときに消えたり増えたりする閉塞区間の数も𝑂(𝑙𝑜𝑔𝐴)個である
方針としてはその時点での閉塞区間をすべて管理する

満点
まずは配列𝐵𝑖 の区間最小値個数のsegment treeに閉塞区間追加、削除の機能=区間加算クエリの機能を追加する
これは遅延segment treeにすればできる満点
𝐴𝑥 を𝑦に更新するクエリ①場所𝑥を含む閉塞区間をすべて削除する（𝑂𝑙𝑜𝑔(𝐴)個）➁ 𝐴𝑥 を𝑦に更新③場所𝑥を含む閉塞区間をすべて見つける（𝑂𝑙𝑜𝑔(𝐴)個）④見つけた閉塞区間を追加する（𝑂𝑙𝑜𝑔(𝐴)個）区間を管理するデータ構造
segment treeに区間を入れていく
区間[𝑙, 𝑟]はその区間を完全に格納できるノードのうち最も小さいものに入れる．

区間を管理するデータ構造
管理する区間は交差しないので、各ノードではそれが対応する範囲を[𝑙, 𝑟]として(𝑙 + 𝑟)/2を含むような区間が入っていく

それらの格納される区間たちは区間の大きい順に次に大きい区間を内包するというように内包の関係が(𝑙 + 𝑟)/2を中心に一列になっている
よって各ノードではstackを持ってそこに区間を小さい順に積んでいく
区間の追加や削除はstackの一番上のみで行う

区間を管理するデータ構造
[1,7]
[4,7]
[4,6]
[1,3]

[2,3]
[5,6]
[4,4]

123

45678

区間を管理するデータ構造①場所𝑥を含む閉塞区間をすべて削除する

Segment treeの葉ノード𝑥から順番に上に上りつつ、各ノードではstackの一番上(一番大きな区間)が𝑥を含む間それらをpopする
𝑂(𝑙𝑜𝑔𝐴 + 𝑙𝑜𝑔𝑁)でできる

区間を管理するデータ構造④見つけた𝑂(𝑙𝑜𝑔𝐴)個の区間を追加する

追加する区間を小さい順に持っておく
Segment treeの葉ノード𝑥から順番に上に上りつつ、各ノードではまだ追加していない区間で最小のものが追加できる間それをpushする
𝑂(𝑙𝑜𝑔𝐴 + 𝑙𝑜𝑔𝑁)

満点③場所xを含む閉塞区間をすべて見つける（𝑂(𝑙𝑜𝑔 𝐴 )個）

満点
場所𝑥の右の壁となる候補は𝐴_𝑥より大きい必要があるのでまず𝑟 < 𝑖かつ𝐴𝑥 < 𝐴𝑟 を満たす最小の𝑟が考えられる

その右で次の候補を考えると，区間は𝑥と𝑟を含むので𝑟 < 𝑟2かつ𝐴𝑥 + 𝐴𝑟 < 𝐴𝑟2 を満たす最小の𝑟2
このように右の候補を求めていくと𝐴の値が2倍になっていくので𝑂(𝑙𝑜𝑔𝐴)個しかない
また〇< 𝑖かつ△< 𝐴𝑖 を満たす最小の𝑖はseg木上の二分探索で𝑂(𝑙𝑜𝑔𝑁)で求まる𝑂(𝑙𝑜𝑔𝐴𝑙𝑜𝑔𝑁)で右の壁の候補をすべて列挙できる

満点同様に左の壁の候補も𝑂(𝑙𝑜𝑔𝐴)個求められる
この左の壁の候補×右の壁の候補の組み合わせをすべて試す
𝑂(𝑙𝑜𝑔𝐴𝑙𝑜𝑔𝐴)細かい話最初に与えられる値も1,1, … , 1（閉塞区間なし）から𝑖番目を𝐴𝑖 に更新するとして𝑁個の更新クエリに帰着すると楽クエリを縮めるパートは壁の候補を列挙するようにすると、計算量は増えるが、区間を見つけるパートと同じ処理でできる
更新クエリで削除、追加するのは更新する場所𝑥が壁になる区間、つまり𝑥 − 1, 𝑥, 𝑥 + 1を含む区間も処理する必要がある．壁の候補も𝑥 −1, 𝑥 + 1から始めて見つけるといい満点（まとめ）
𝐴𝑥 を𝑦に更新するクエリ①場所𝑥を含む閉塞区間をすべて削除する(𝑙𝑜𝑔𝐴個)区間の管理𝑂(𝑙𝑜𝑔𝐴 + 𝑙𝑜𝑔𝑁)、Bの配列の更新𝑂(𝑙𝑜𝑔𝐴𝑙𝑜𝑔𝑁)➁ 𝐴𝑥 を𝑦に更新③場所𝑥を含む閉塞区間をすべて見つける（𝑙𝑜𝑔𝐴個）𝑂(𝑙𝑜𝑔𝐴𝑙𝑜𝑔𝑁 + 𝑙𝑜𝑔𝐴𝑙𝑜𝑔𝐴)④見つけた閉塞区間を追加する（𝑙𝑜𝑔𝐴個）区間の管理𝑂(𝑙𝑜𝑔𝐴 + 𝑙𝑜𝑔𝑁)、Bの配列の更新𝑂(𝑙𝑜𝑔𝐴𝑙𝑜𝑔𝑁)満点（まとめ）[𝐿, 𝑅]にこたえるクエリ⑤左右で新たにできる閉塞区間に含まれる部分を除く 𝑂(𝑙𝑜𝑔𝑁)⑥配列𝐵(各場所が含む閉塞区間の数)で区間最小値の個数を求める𝑂(𝑙𝑜𝑔𝑁)全体で𝑂((𝑁 + 𝑄)(𝑙𝑜𝑔𝑁𝑙𝑜𝑔𝐴 + 𝑙𝑜𝑔𝐴𝑙𝑜𝑔𝐴))

得点分布
48点
36点
25点
13点

8点
5点
0点