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

题目描述

水羊羹是一种日本甜点，是用红豆糊和琼脂制成的。它的做法是先将红豆糊与琼脂混合后搅拌均匀，然后倒入长方形模具中，等待它们凝固成型。

现在，JOI 君有了一个制作水羊羹的机器。他可以用该机器制作一块长度为 $d_1+d_2+⋯+d_N$ 的水羊羹。JOI 君可以让这块水羊羹沿着 $N−1$ 条垂直的切割线（不包括两端）分割成 $N$ 段长度为 $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$ 场茶会中的所选小片的最大数量。

输入输出样例 #1

输入 #1

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

输出 #1

3

输入输出样例 #2

输入 #2

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

输出 #2

1
2
3

说明/提示

对于所有输入数据，满足：

• $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$

详细子任务附加限制及分值如下表所示。