P9334 [JOIST 2023] 水羊羹 2 / Mizuyokan 2

水羊羹是一种用红豆沙制成的日式点心，将红豆沙与琼脂混合，并用矩形模具定型，这样就可以做成水羊羹了。 现在 JOI 君有一台 **水羊羹机器**。使用它，JOI 君可以制作一个横向的矩形水羊羹，其上有 $N-1$ 条垂直切割线。水羊羹的长度和切割线位置由机器上设置的 $N$ 个参数 $d_1,d_2,\ldots,d_N$ 确定。水羊羹的长度为 $d_1+d_2+\ldots+d_N$。从左到右第 $(i-1)\ (1\le i\le N)$ 条切割线与第 $i$ 条切割线之间的距离为 $d_i$。这里，我们考虑水羊羹的最左边为第 $0$ 条切割线，水羊羹的最右边为第 $N$ 条切割线。最初，水羊羹机器的参数满足 $d_i=L_i\ (1\le i\le N)$。 JOI 君计划组织 $Q$ 次茶会。第 $j\ (1\le j\le Q)$ 次茶会由整数 $X_j,Y_j,A_j,B_j$ 表示。茶会按如下方式进行： - 水羊羹机器的参数 $d_{X_j}$ 被更新，并设置为 $Y_j$。 - JOI 君用水羊羹机器只做了一个新的水羊羹。他把水羊羹在第 $A_j$ 条切割线和第 $B_j$ 条切割线之间的部分取出，用于茶会。他吃掉了剩余部分。 - JOI 君沿一些切割线来切为茶会准备的水羊羹。他会将水羊羹切为一或更多块。在这个过程中应满足以下条件：如果这些切好的水羊羹块按最初的位置从左到右排列，那么这些水羊羹块的长度序列应该是 **锯齿形** 的。 这里，如果序列中元素交替上升和下降，就称这个序列是锯齿形的。例如，序列 $(2,9,2,7),(7,1,9,4,6),(5),(2,1)$ 是锯齿形的，但序列 $(1,2,3),(7,1,4,4,6),(2,2)$ 不是锯齿形的。准确地说，一个序列 $(x_1,x_2,\ldots,x_m)$ 被称为锯齿形的，当且仅当以下条件中至少一个被满足： - 对于 $k=1,2,\ldots,m-1$，当 $k$ 为奇数时满足不等式 $x_k < x_{k+1}$，当 $k$ 为偶数时满足不等式 $x_k > x_{k+1}$。 - 对于 $k=1,2,\ldots,m-1$，当 $k$ 为奇数时满足不等式 $x_k > x_{k+1}$，当 $k$ 为偶数时满足不等式 $x_k < x_{k+1}$。 因为 JOI 君想要把水羊羹给尽可能多的朋友们，他想最大化步骤 $3$ 中得到的水羊羹数。 给定初始水羊羹机器的参数和茶会计划，写一个程序计算对于每次茶会，在满足条件的情况下最多能得到的最大水羊羹数。注意，在本题的限制下，满足条件的水羊羹切分方法必然存在。

从标准输入中读入以下数据： > $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$ 场茶会中的所选小片的最大数量。

对于所有输入数据，满足： - $1\le N \le 2.5\times 10^5$ - $1\le L_i \le 10^9$ - $1\le Q\le5\times10^4$ - $1\le X_j\le N,1\le Y_j\le 10^9$ - $0\le A_j < B_j \le N$ 详细子任务附加限制及分值如下表所示。 |子任务编号|附加限制|分值 | |:---:|:--------:|:-:| |$1$|$N\le 200,Q\le 10$| $6$| |$2$|$N\le 2\space000,Q\le 10$| $9$| |$3$|$Q\le10$|$13$| |$4$|$Y_j=L_{X_j}$|$32$| |$5$|$L_i,Y_j\le 1.2\times10^5$|$29$| |$6$|无附加限制|$11$|