[JOISC 2023 Day2] Mizuyokan 2

#### 题目描述 水羊羹是一种日本甜点，是用红豆糊和琼脂制成的。它的做法是先将红豆糊与琼脂混合后搅拌均匀，然后倒入长方形模具中，等待它们凝固成型。 现在，JOI 君有了一个制作水羊羹的机器。他可以用该机器制作一块长度为 $d_1+d_2+⋯+d_N$ 的水羊羹。JOI 君可以让这块水羊羹沿着 $N−1$ 条垂直的切割线（不包括两端）分割成 NN 段长度为 $d_1,d_2,…,d_N$ 的竖条形状的小片。 JOI 君希望在有 $Q$ 场茶会上送给尽可能多的朋友水羊羹。每场茶会对应 $(X_j,Y_j,A_j,B_j)$，其中： + JOI 君会更新机器上第 $X_j$ 条切割线的位置为 $Y_j$，以此生成一个新的水羊羹。 + JOI 君挑选出原水羊羹中从第 $A_j$ 条切割线到第 $B_j$ 条切割线之间的部分，作为茶会中的水羊羹。剩余部分被他自己吃掉。 + JOI 君需将所选小片沿着一些切割线分割成若干段让朋友品尝。在这一过程中应当满足如下条件：如果按顺序排列，分割后每个小片长度的大小应当是一个“之”字形，即连续两个片段长度先递增再递减，亦或者先递减再递增。 具体地，令 $(x_1,x_2,…,x_m)$ 是分割后小片长度组成的序列，$(x_1,x_2,…,x_m)$ 是“之”字形当且仅当它满足以下一个或两个条件： + 对于所有 $k=1,2,…,m−1$，如果 $k$ 为奇数，则 $x_k<x_{k+1}$，否则 $x_k>x_{k+1}$。 + 对于所有 $k=1,2,…,m−1$，如果 $k$ 为奇数，则 $x_k>x_{k+1}$，否则 $x_k<x_{k+1}$。 因为 JOI 君希望给尽可能多的朋友品尝到水羊羹，所以他希望供品的小片数量最大化。 请完成一个程序，它会读入水羊羹机器的参数和茶会计划，并对每一场茶会输出可供品尝的小片的最大数量。请注意，在任务的限制下，可以总是找到一种合适的方法将所选小片分割成符合“之”字形条件的若干小片。 #### 输入格式 从标准输入中读入以下数据： > $N$ > > $L_1 \ L_2 \ \cdots \ L_N$ > > $Q$ > > $X_1 \ Y_1 \ A_1 \ B_1$ > > $X_2 \ Y_2 \ A_2 \ B_2$ > > $\vdots$ > > $X_Q \ Y_Q \ A_Q \ B_Q$ #### 输出格式 程序应该在标准输出中输出 $Q$ 行。第 $j$ 行 $(1≤j≤Q)$ 应当包含第 $j$ 场茶会中的所选小片的最大数量。 Translate by @[ZeXic_B](https://www.luogu.com.cn/user/661274)

Mizuyokan is a Japanese confectionery made of azuki beans paste. It was made by cooking azuki beans paste with agar, and solidifying them in a rectangular-shaped form. Now, JOI-kun has a mizuyokan machine. Using it, JOI-kun can make a horizontally long rectangular-shaped mizuyokan with $N - 1$ vertical cutlines. The length of the mizuyokan and the positions of the cutlines are determined by the $N$ parameters $d_1, d_2, \dots, d_N$ set on the machine. The length of the mizuyokan is $d_1 + d_2 + \dots + d_N$. The distance between the $(i - 1)$-th cutline $(1 \le i \le N)$ from the left and the $i$-th cutline from the left is $d_i$. Here, we consider the leftmost edge of the mizuyokan as the $0$-th cutline, and the rightmost edge of the mizuyokan as the $N$-th cutline. In the beginning, the parameters of the mizuyokan machine satisfy $d_i = L_i \ (1 \le i \le N)$. JOI-kun has a plan to organize $Q$ tea parties. The $j$-th tea party $(1 \le j \le Q)$ is described by the integers $X_j, Y_j, A_j, B_j$. It proceeds as follows. 1. The parameter $d_{X_j}$ of the mizuyokan machine is updated, and it is set as $Y_j$. 2. JOI-kun makes a new mizuyokan using the mizuyokan machine. He takes the part of the mizuyokan 0between the $A_j$-th cutline and the $B_j$-th cutline, and uses it for the tea party. He eats the rest. 3. JOI-kun cuts the part of the mizuyokan for the tea party along some of the cutlines. He cuts the part of the mizuyokan into one or more pieces. In this process, the following condition should be satisfied: if the pieces are ordered from the left as in the original positions, the sequence of the lengths of the pieces is **zigzag**. Here, a sequence is called zigzag if the elements of the sequence increase and decrease alternately. For example, the sequences $(2, 9, 2, 7), (7, 1, 9, 4, 6), (5), (2, 1)$ are zigzag, but the sequences $(1, 2, 3), (7, 1, 4, 4, 6), (2, 2)$ are not zigzag. Precisely, a sequence $(x_1, x_2, \dots, x_m)$ is called zigzag if one (or the both) of the following conditions are satisfied: - For $k = 1, 2, \dots, m - 1$, the inequality $x_k < x_{k + 1}$ is satisfied if $k$ is odd, and the inequality $x_k > x_{k + 1}$ is satisfied if $k$ is even. - For $k = 1, 2, \dots, m - 1$, the inequality $x_k > x_{k + 1}$ is satisfied if $k$ is odd, and the inequality $x_k < x_{k + 1}$ is satisfied if $k$ is even. Since JOI-kun wants to give mizuyokan to as many friends as possible, he wants to maximize the number of pieces obtained by the procedure 3. of the tea party. Write a program which, given information of the initial parameters of the mizuyokan machine and the plan of the tea parties, calculates, for each tea party, the maximum possible number of pieces obtained by cutting the part of the mizuyokan so that the condition is satisfied. Note that, under the constraints of this task, it is always possible to cut the part of the mizuyokan so that the condition is satisfied.

Read the following data from the standard input. > $N$ > > $L_1 \ L_2 \ \cdots \ L_N$ > > $Q$ > > $X_1 \ Y_1 \ A_1 \ B_1$ > > $X_2 \ Y_2 \ A_2 \ B_2$ > > $\vdots$ > > $X_Q \ Y_Q \ A_Q \ B_Q$

Write $Q$ lines to the standard output. The $j$-th line $(1 \le j \le Q)$ of output corresponds to the $j$-th tea party. It contains the maximum possible number of pieces obtained by cutting the part of the mizuyokan in the $j$-th tea party so that the condition is satisfied.

6
5 6 8 7 4 9
1
6 9 0 5

3

4
6 2 3 6
3
3 2 1 3
4 5 1 4
1 1 0 4

1
2
3

**【样例解释 #1】** In the first tea party, the parameters of the mizuyokan machine is set as $(d_1, d_2, d_3, d_4, d_5, d_6) = (5, 6, 8, 7, 4, 9)$. JOI-kun uses the part of the mizuyokan between the $0$-th cutline and the $5$-th cutline as in Figure 1.  For example, JOI-kun can cut the part of the mizuyokan as follows.  In Method 1, the lengths of the pieces are $5, 14, 7, 4$. Since this sequence is not zigzag, it does not satisfy the condition. On the other hand, in Method 2, the lengths of the pieces are $11, 8, 11$. Since this sequence is zigzag, it satisfies the condition. In Method 3, the length of the piece is $30$. Since this sequence is zigzag, it also satisfies the condition. If JOI-kun cuts the part of the mizuyokan by Method 2, he gets $3$ pieces. Since it is not possible for him to cut the part of the mizuyokan so that the condition is satisfied and he gets more than or equal to $4$ pieces, output $3$ in the first line. 该样例满足所有子任务的限制。 **【样例解释 #2】** In the first tea party, the length of the part of the mizuyokan for the tea party is $4$. There is a cutline whose distance is $2$ from the leftmost edge. If JOI-kun uses the mizuyokan without cutting it, he gets one piece. The sequence of the lengths of the pieces is $(4)$, which is zigzag. Since he cannot obtain more than one pieces, output $1$. In the second tea party, the length of the part of the mizuyokan for the tea party is $9$. There are two cutlines whose distances are $2, 4$ from the leftmost edge. If JOI-kun cuts the mizuyokan at the cutline whose distance is $4$ from the leftmost edge, he gets two pieces. The sequence of the lengths of the pieces is $(4, 5)$, which is zigzag. Since he cannot obtain more than two pieces, output $2$. In the third tea party, the length of the part of the mizuyokan for the tea party is $10$. There are three cutlines whose distances are $1, 3, 5$ from the leftmost edge. If JOI-kun cuts the mizuyokan at the cutlines whose distances are $3, 5$ from the leftmost edge, he gets three pieces. The sequence of the lengths of the pieces is $(3, 2, 5)$, which is zigzag. Since he cannot obtain more than three pieces, output $3$. 该样例满足子任务 $1, 2, 3, 5, 6$ 的限制。 **【数据范围】** 对于所有测试数据，满足 $1 \le N \le 2.5 \times 10 ^ 5$，$1 \le L_i \le 10 ^ 9$，$1 \le Q \le 5 \times 10 ^ 4$，$1 \le X_j \le N$，$1 \le Y_j \le 10 ^ 9$，$0 \le A_j < B_j \le N$，保证所有输入均为整数。 |子任务编号|分值|限制| |:-:|:-:|:-:| |$1$|$6$|$N \le 200$，$Q \le 10$| |$2$|$9$|$N \le 2000$，$Q \le 10$| |$3$|$13$|$Q \le 10$| |$4$|$32$|$Y_j = L_{X_j}$| |$5$|$29$|$L_i, Y_j \le 1.2 \times 10 ^ 5$| |$6$|$11$|无|