#P11699. [ROIR 2025] 酸雨

[ROIR 2025] 酸雨

题目背景

翻译自 ROIR 2025 D1T3

题目描述

nn 个模块被运送到金星上用于组装实验室。模块按顺序排列,第 ii 个模块的高度为 hih_i

组装工作将由一台特殊的机器人来完成。在组装过程中,连续的模块段将逐渐合并,而模块在排列中的顺序不会改变。最初,每个模块都是一个独立的段,段的编号从 11nn,与模块的编号顺序相同。如果有两个相邻的模块段 A=[i,i+1,,i+p1]A = [i, i+1, \dots, i+p-1]B=[i+p,i+p+1,,i+p+q1]B = [i+p, i+p+1, \dots, i+p+q-1],那么它们合并后变成段 $AB = [i, i+1, \dots, i+p-1, i+p, i+p+1, \dots, i+p+q-1]$。

组装指令由 n1n-1 条指令组成。每条指令包含一个数字 kjk_j。执行该指令后,编号为 kjk_jkj+1k_j + 1 的模块段合并为一个新段,合并后的段占据原来两个段的位置,并重新对段进行编号,从 kj+2k_j + 2 开始,后面的段的编号依次减 11。执行完所有指令后,所有段将合并为一个段。

金星上常年下酸雨,因此在组装过程中,必须在每次合并后了解每个段中可能积累的液体量。设一个段包含高度为 hl,hl+1,,hrh_l, h_{l+1}, \dots, h_r 的模块。对于其中任意一个模块 pp,其中 lprl \leq p \leq r,我们定义该模块 pp 在该段的深度 dpd_p 如下:

首先计算左侧最大高度 lp=max{hl,hl+1,,hp}l_p = \max\{ h_l, h_{l+1}, \dots, h_p \} 和右侧最大高度 rp=max{hp,hp+1,,hr}r_p = \max\{ h_p, h_{p+1}, \dots, h_r \}。这分别是该段中模块 pp 左侧和右侧的最大高度。该模块 pp 的深度定义为 dp=min(lp,rp)hpd_p = \min(l_p, r_p) - h_p,显然 dp>0d_p > 0。段的容量定义为该段所有模块的深度之和,即 w=dl+dl+1++drw = d_l + d_{l+1} + \dots + d_r

给定一系列合并操作,请在每次合并后输出合并段的容量。

输入格式

第一行包含一个整数 nn,表示模块的数量(2n1052 \leq n \leq 10^5)。

第二行包含 nn 个整数 h1,h2,,hnh_1, h_2, \dots, h_n1hi1091 \leq h_i \leq 10^9),表示每个模块的高度。

第三行包含 n1n-1 个整数,表示合并操作的指令,每个指令用一个整数 kjk_j 表示(1kjnj1 \leq k_j \leq n-j)。

输出格式

输出 n1n-1 个整数,用换行隔开,表示每次合并后,合并段的容量。

8
9 1 8 1 5 2 3 6
3 3 1 3 3 2 1

0
4
0
0
0
13
20

提示

下图显示了样例中指令执行的过程,每个模块上方标出了其深度,并显示了新段的容量。

本题使用 Subtask 捆绑测试。数据中 Subtask 0 是样例。

子任务 分数 特殊性质
11 1313 n100n \leq 100
22 n1000n \leq 1000
33 hi10h_i \leq 10
44 $\exist i,h_1 \ge h_2 \ge \dots \ge h_i \leq \dots \leq h_n$
55 77 所有查询中 kj=1k_j = 1
66 1313 n40000n \leq 40000
77 2828