水ようかん 2 (Mizuyokan 2) 解説
平木 康傑

1

問題概要

長さ の正の整数列がある．
「 を に更新」「連続部分列に対して以下の問題を解く」の つのクエリを処理せよ．
問題: パートごとの総和がジグザグになるように分割するとき，最大で何個に分割できる？
ジグザグとは，(狭義の)増加・減少が交互に起こることとする．

mizuyokan2

解説

2

例

をジグザグに分割する方法を考える．のように分割すると，となるので条件を満たす．のように分割すると，となる． は狭義の増加・減少ではないので，条件を満たさない．

mizuyokan2

解説3

言葉はあった方が便利

和が大きい方のパートを「山」，和が小さい方のパートを「谷」と呼ぶことにする．

谷，山， 谷， 山， 谷．
mizuyokan2

解説という分割なら4小課題，，

1.
2.
3.

更新なし
5. 数列の要素は以下
6. 追加の制約はない小課題 は区間 DP で，小課題 はその高速化で解ける．
4.

mizuyokan2

解説5

考察 -a: つの山の間にある谷について，両隣の山をのばすことで，谷の長さを にできる．

mizuyokan2

解説6

考察 -b: 端にある谷について，隣の山を適切にのばすことで，谷の長さを にできる．

mizuyokan2

解説7

考察 : 任意の valid な分割に対して，山を適切にのばせば，もとと同じ分割個数で谷の長さがすべて であるような valid な分割が作れる．

つまり，谷の長さが であるような分割のみを考えれば十分．

mizuyokan2

解説8

考察 +: 谷の長さが であるような分割のみを考えれば十分．
次のような DP をすればよい::=が谷であるときの，そこまでの分割個数の最大値．
を満たす は，の形で表せる．
を満たす は，の形で表せる．
上の性質から，セグメント木などを使った高速化が効く(詳細略)．
小課題 () は通る．

mizuyokan2

解説9

谷と山の両方が絡むとややこしい
先ほどは「谷」のみに注目する方針をとった．
「山」のみに注目する方針が取れないか？

mizuyokan2

解説10

山のみに注目したい

両隣の要素のみを見て判断できるような山の亜種を考える．
(とする)を満たすような区間 を和歌山と呼ぶことにする．
山は必ず和歌山である．

mizuyokan2

解説11

考察 : 任意の valid な分割に対して，山を適切にのばせば，もとと同じ分割個数で谷の長さがすべて であるような valid な分割が作れる．
仮説 : 任意の valid な和歌山分割に対して，和歌山を適切にのばせば，分割個数を減らさずに，谷の長さがすべて であるような valid な分割が作れる．
ここで和歌山分割は，和歌山を満たすようなものとする．

mizuyokan2

解説の取り方であって12

考察 -a: つの和歌山の間の谷モドキについて，どちらかの和歌山をのばすことで，長さの谷にできる．

mizuyokan2

解説13

考察 -b: 端にある谷モドキについて，隣の和歌山をのばすことで，長さ の谷にできる．

mizuyokan2

解説14

考察 : 任意の valid な和歌山分割に対して，和歌山を適切にのばせば，分割個数を減らさずに，谷の長さがすべて であるような valid な分割が作れる．

mizuyokan2

解説15

考察 +: 和歌山分割の最大個数は，分割の最大個数と一致する．
考察 +: 谷の長さが であるような分割のみを考えれば十分．
考察 : 任意の valid な和歌山分割に対して，和歌山を適切にのばせば，分割個数を減らさずに，谷の長さがすべて であるような valid な分割が作れる．
小考察: valid な分割は，和歌山分割としても valid．
mizuyokan2

解説16

考察 +: 和歌山分割の最大個数は，分割の最大個数と一致する．
ある区間が山であるかは，前後の山の選び方に依存する．
ある区間が和歌山であるかは，その区間と両隣の要素の値しか関係しない(そこだけ見れば判断できる！)
つまり，もともと考えていた分割よりも和歌山分割のほうが扱いやすい．

mizuyokan2

解説17

和歌山分割はある区間が和歌山であるかは，その区間と両隣の要素の値だけが関係する．
和歌山として valid な区間 がたくさん与えられるので，を被らないように選べばよい．

mizuyokan2

解説18

和歌山分割は区間スケジューリング

ある区間が和歌山であるかは，その区間と両隣の要素の値だけが関係する．
和歌山として valid な区間 がたくさん与えられるので，を被らないように選べばよい．
区間スケジューリングに帰着された．
区間スケジューリングは，選べるもののうち が最小のものを貪欲に選ぶのが最適解．
和歌山分割に言い換える前の分割では貪欲法は誤りなので注意．

mizuyokan2

解説19

小課題 : 値は更新されない直前の から飛べる次の の最小値を とする．
次の区間をとおくと，の場合はでカバーできるので，の場合のみを求めればよい．
を満たす最大の を求めればよい．
端の処理に注意．端の山・谷の組合せを 通り試すと確実．

mizuyokan2

解説20

小課題 : 値は更新されない直前の から飛べる次の の最小値を とする．
を満たす最大の を求めればよい(端の処理に注意)．
値が更新されないので，ダブリングによって各クエリが時間で処理できる．
ダブリング:を利用してを前計算できるうえ，を満たす最大の が二分探索で求まる．

mizuyokan2

解説

21

小課題:

値は更新される一点更新とはいえ，それを含むすべての区間に影響するので，が変わる は多いのではないか？

mizuyokan2

解説22

考察 : 一度に飛ぶ距離．

は，高々とする．
() が成り立つとすると，( 帰納法で示せる ) よりとなり，矛盾．
したがって，が少なくとも ヶ所ので成り立つ．
同様にが少なくとも ヶ所ので成り立つ．

mizuyokan2

解説23

考察 : 一度に飛ぶ距離．

は，高々とする．
が少なくとも ヶ所ので成り立つことが示せた．
同様に，が少なくとも ヶ所ので成り立つことも示せ
る．
したがって，を満たす和歌山の区間が存在する．

mizuyokan2

解説24

これで更新クエリがラクになるを一点更新したとき， が変わりうるのはの範囲のみ．
愚直にやっても時間で済むし，小課題 と同様にを利用する方針でいけば時間になる．

mizuyokan2

解説25

トドメのセグメント木から出発して を超えないように繰り返し飛ぶとき，最大何回でどこまで飛ぶか必要な の範囲はの二項演算は時間．
を利用すれば，個ある それぞれについてが定数時間で求まるため．
セグ木の更新と区間取得は，セグ木区間の合成を回行うのでともに時間．
:=

mizuyokan2

解説26

以上より，この問題は谷を長さ につぶす方法を思いつき，

mizuyokan2

解説27

以上より，この問題は谷を長さ につぶす方法を思いつき，谷ではなく山に注目することで区間スケジューリングに帰着し，mizuyokan2

解説28以上より，この問題は谷を長さ につぶす方法を思いつき，谷ではなく山に注目することで区間スケジューリングに帰着し，必要な区間の長さが高々であることに気付いて，

mizuyokan2

解説29以上より，この問題は谷を長さ につぶす方法を思いつき，谷ではなく山に注目することで区間スケジューリングに帰着し，必要な区間の長さが高々であることに気付いて，ダブリングの考え方をセグメント木に乗せることで，クエリあたり時間で解くことができました！

mizuyokan2

解説30

やっべスライド作るの間に合わないスクショ載せます

mizuyokan2

解説31