The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)
Spring Training/Qualifying Trial
March 18–22, 2023 (Komaba, Tokyo)
Contest 2 – Mizuyokan 2

水ようかん 2 (Mizuyokan 2)

水ようかんとは，おもに小豆からなる餡を型に流し込んで寒天で固めることにより作られる和菓子である．
いま，JOI 君の手元には水ようかん製造機がある．この水ようかん製造機は横長の直方体の形をした水ようかんを製造し，その水ようかんには縦方向の切れ目が N − 1 箇所に入る．水ようかんの長さと切れ目の位
置は，水ようかん製造機に設定されている N 個のパラメータ d1 , d2 , . . . , dN によって定まる．水ようかんの長さは d1 + d2 + · · · + dN であり，左から i − 1 番目と i 番目 (1 ≦ i ≦ N) の切れ目の間の長さは di である．
ただし，水ようかんの左端を 0 番目の切れ目，右端を N 番目の切れ目とみなす．はじめ，水ようかん製造機のパラメータは di = Li (1 ≦ i ≦ N) に設定されている．

JOI 君は Q 回のお茶会を計画している． j 回目 (1 ≦ j ≦ Q) のお茶会の内容は整数 X j , Y j , A j , B j で表され，その手順は以下の通りである．

1. 水ようかん製造機のパラメータ dX j の値を Y j に更新する．
2. 水ようかん製造機で，新しい水ようかんを 1 つ製造し，A j 番目の切れ目から B j 番目の切れ目の間の部分を切り出し，お茶会に使用する．残りの部分は JOI 君が食べる．

3. お茶会に使用する部分の水ようかんを，いくつかの切れ目に沿って 1 個以上のピースに切り分ける．
このとき，得られるピースの長さをそのピースのもともとの位置が左にあるものから順に並べた数列がジグザグになる，という条件を満たすようにする．
ただし，数列がジグザグであるとは，数列の要素が増加と減少を交互に繰り返していることをいう．例えば，数列 (2, 9, 2, 7)，(7, 1, 9, 4, 6)，(5)，(2, 1) はジグザグであるが，数列 (1, 2, 3)，(7, 1, 4, 4, 6)，(2, 2) はジグザグではない．厳密には，数列 (x1 , x2 , . . . , xm ) がジグザグであるとは，その数列が以下の 2 つの条件のいずれかを満たすことをいう．

• k = 1, 2, . . . , m − 1 に対して，k が奇数ならば xk < xk+1 を，k が偶数ならば xk > xk+1 を満たす．
• k = 1, 2, . . . , m − 1 に対して，k が奇数ならば xk > xk+1 を，k が偶数ならば xk < xk+1 を満たす．
JOI 君は，できるだけ多くの友達に水ようかんをふるまうため，それぞれのお茶会の手順 3. において得られるピースの個数をできるだけ多くしたい．
水ようかん製造機のパラメータの初期値とお茶会の計画の情報が与えられるので，それぞれのお茶会において，条件を満たすような切り分け方で得られるピースの個数の最大値を求めるプログラムを作成せよ．な
お，この問題の制約下では，条件を満たすように水ようかんを切り分ける方法が必ず存在する．

水ようかん 2– 1 / 4

The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)
Spring Training/Qualifying Trial
March 18–22, 2023 (Komaba, Tokyo)
Contest 2 – Mizuyokan 2

入力
入力は以下の形式で標準入力から与えられる．

N
L1 L2 · · · LN
QX1 Y1 A1 B1X2 Y2 A2 B2..
.
X Q Y Q A Q BQ

出力
標準出力に Q 行出力せよ． j 行目 (1 ≦ j ≦ Q) には， j 回目のお茶会において，条件を満たすような切り分け方で得られるピースの個数の最大値を出力せよ．

制約• 1 ≦ N ≦ 250 000．
• 1 ≦ Li ≦ 109 (1 ≦ i ≦ N)．
• 1 ≦ Q ≦ 50 000．
• 1 ≦ X j ≦ N (1 ≦ j ≦ Q)．
• 1 ≦ Y j ≦ 109 (1 ≦ j ≦ Q)．
• 0 ≦ A j < B j ≦ N (1 ≦ j ≦ Q)．
• 入力される値はすべて整数である．

水ようかん 2– 2 / 4

The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)
Spring Training/Qualifying Trial
March 18–22, 2023 (Komaba, Tokyo)
Contest 2 – Mizuyokan 2小課題
1. (6 点) N ≦ 200，Q ≦ 10．
2. (9 点) N ≦ 2 000，Q ≦ 10．
3. (13 点) Q ≦ 10．
4. (32 点) Y j = LX j (1 ≦ j ≦ Q)．
5. (29 点) Li ≦ 120 000 (1 ≦ i ≦ N)，Y j ≦ 120 000 (1 ≦ j ≦ Q)．
6. (11 点) 追加の制約はない．

入出力例
入力例 1

出力例 1635 6 8 7 4 9
16 9 0 5
1 回目のお茶会において，水ようかん製造機のパラメータは (d1 , d2 , d3 , d4 , d5 , d6 ) = (5, 6, 8, 7, 4, 9) となる．
お茶会には，表 1 に示すような 0 番目の切れ目と 5 番目の切れ目の間の部分を使用する．
表 1 お茶会で使用する水ようかん．

56874

例えば，表 2 のような切り分け方が考えられる．
表 2 水ようかんの切り分け方の例 3 つ．上から方法 1, 2, 3 とする．

568745687456874

方法 1 ではピースの長さが順に 5, 14, 7, 4 となっており，この数列はジグザグではないので条件を満たさない．一方，方法 2 ではピースの長さが順に 11, 8, 11 となっており，この数列はジグザグであるため条件を満たす．また，方法 3 ではピースの長さが順に 30 となっており，この数列もジグザグであるため条件を満たす．

水ようかん 2– 3 / 4

The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)
Spring Training/Qualifying Trial
March 18–22, 2023 (Komaba, Tokyo)Contest 2 – Mizuyokan 2
方法 2 のようにして，条件を満たすような切り分け方で 3 個のピースを得ることができる．また，条件を満たすような切り分け方で 4 個以上のピースを得ることはできない．よって，1 行目には 3 を出力する．
この入力例はすべての小課題の制約を満たす．
入力例 2出力例 2416 2 3 62333 2 1 34 5 1 41 1 0 4
1 回目のお茶会では，お茶会に使用する水ようかんの長さは 4 であり，左から長さ 2 の位置に切れ目がある．このとき，切り分けずにそのまま使用することで 1 個のピースが得られる．得られるピースの長さを順に並べた数列は (4) であり，これはジグザグである．これよりも多くのピースを得ることはできないので，1 を出力する．
2 回目のお茶会では，お茶会に使用する水ようかんの長さは 9 であり，左から長さ 2, 4 の位置に切れ目がある．このとき，左から長さ 4 の位置の切れ目で切ることで，2 個のピースが得られる．得られるピースの長さを順に並べた数列は (4, 5) であり，これはジグザグである．これよりも多くのピースを得ることはできないので，2 を出力する．

3 回目のお茶会では，お茶会に使用する水ようかんの長さは 10 であり，左から長さ 1, 3, 5 の位置に切れ目がある．このとき，左から長さ 3, 5 の位置の切れ目で切ることで，3 個のピースが得られる．得られるピースの長さを順に並べた数列は (3, 2, 5) であり，これはジグザグである．これよりも多くのピースを得ることはできないので，3 を出力する．
この入力例は小課題 1, 2, 3, 5, 6 の制約を満たす．

水ようかん 2– 4 / 4