{"problem":{"name":"[JOIST 2023] 水羊羹 2 / Mizuyokan 2","description":{"content":"水羊羹是一种用红豆沙制成的日式点心，将红豆沙与琼脂混合，并用矩形模具定型，这样就可以做成水羊羹了。 现在 JOI 君有一台 **水羊羹机器**。使用它，JOI 君可以制作一个横向的矩形水羊羹，其上有 $N-1$ 条垂直切割线。水羊羹的长度和切割线位置由机器上设置的 $N$ 个参数 $d_1,d_2,\\ldots,d_N$ 确定。水羊羹的长度为 $d_1+d_2+\\ldots+d_N$。从左到右第","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9334"},"statements":[{"statement_type":"Markdown","content":"水羊羹是一种用红豆沙制成的日式点心，将红豆沙与琼脂混合，并用矩形模具定型，这样就可以做成水羊羹了。\n\n现在 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)$。\n\nJOI 君计划组织 $Q$ 次茶会。第 $j\\ (1\\le j\\le Q)$ 次茶会由整数 $X_j,Y_j,A_j,B_j$ 表示。茶会按如下方式进行：\n\n- 水羊羹机器的参数 $d_{X_j}$ 被更新，并设置为 $Y_j$。\n- JOI 君用水羊羹机器只做了一个新的水羊羹。他把水羊羹在第 $A_j$ 条切割线和第 $B_j$ 条切割线之间的部分取出，用于茶会。他吃掉了剩余部分。\n- JOI 君沿一些切割线来切为茶会准备的水羊羹。他会将水羊羹切为一或更多块。在这个过程中应满足以下条件：如果这些切好的水羊羹块按最初的位置从左到右排列，那么这些水羊羹块的长度序列应该是 **锯齿形** 的。\n\n这里，如果序列中元素交替上升和下降，就称这个序列是锯齿形的。例如，序列 $(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)$ 被称为锯齿形的，当且仅当以下条件中至少一个被满足：\n\n- 对于 $k=1,2,\\ldots,m-1$，当 $k$ 为奇数时满足不等式 $x_k < x_{k+1}$，当 $k$ 为偶数时满足不等式 $x_k > x_{k+1}$。\n- 对于 $k=1,2,\\ldots,m-1$，当 $k$ 为奇数时满足不等式 $x_k > x_{k+1}$，当 $k$ 为偶数时满足不等式 $x_k < x_{k+1}$。\n\n因为 JOI 君想要把水羊羹给尽可能多的朋友们，他想最大化步骤 $3$ 中得到的水羊羹数。\n\n给定初始水羊羹机器的参数和茶会计划，写一个程序计算对于每次茶会，在满足条件的情况下最多能得到的最大水羊羹数。注意，在本题的限制下，满足条件的水羊羹切分方法必然存在。\n\n## Input\n\n从标准输入中读入以下数据：\n\n> $N$\n>\n> $L_1 \\ L_2 \\ \\cdots \\ L_N$\n>\n> $Q$\n>\n> $X_1 \\ Y_1 \\ A_1 \\ B_1$\n>\n> $X_2 \\ Y_2 \\ A_2 \\ B_2$\n>\n> $\\vdots$\n>\n> $X_Q \\ Y_Q \\ A_Q \\ B_Q$\n\n## Output\n\n程序应该在标准输出中输出 $Q$ 行。第 $j$ 行 $(1≤j≤Q)$ 应当包含第 $j$ 场茶会中的所选小片的最大数量。\n\n[samples]\n\n## Note\n\n对于所有输入数据，满足：\n\n- $1\\le N \\le 2.5\\times 10^5$\n- $1\\le L_i \\le 10^9$\n- $1\\le Q\\le5\\times10^4$\n- $1\\le X_j\\le N,1\\le Y_j\\le 10^9$\n- $0\\le A_j < B_j \\le N$\n\n详细子任务附加限制及分值如下表所示。\n\n|子任务编号|附加限制|分值 |\n|:---:|:--------:|:-:|\n|$1$|$N\\le 200,Q\\le 10$| $6$|\n|$2$|$N\\le 2\\space000,Q\\le 10$| $9$|\n|$3$|$Q\\le10$|$13$|\n|$4$|$Y_j=L_{X_j}$|$32$|\n|$5$|$L_i,Y_j\\le 1.2\\times10^5$|$29$|\n|$6$|无附加限制|$11$|","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9334","tags":["2023","O2优化","JOISC/JOIST（日本）"],"sample_group":[["6\n5 6 8 7 4 9\n1\n6 9 0 5\n","3\n"],["4\n6 2 3 6\n3\n3 2 1 3\n4 5 1 4\n1 1 0 4\n","1\n2\n3\n"]],"created_at":"2026-03-03 11:09:25"}}