小美是美团仓库的管理员，她会根据单据的要求按顺序取出仓库中的货物，每取出一件货物后会把剩余货物重新堆放，使得自己方便查找。已知货物入库的时候是按顺序堆放在一起的。如果小美取出其中一件货物，则会把货物所在的一堆物品以取出的货物为界分成两堆，这样可以保证货物局部的顺序不变。 已知货物最初是按1~n的顺序堆放的，每件货物的重量为w_i,小美会根据单据依次不放回的取出货物。请问根据上述操作，小美每取出一件货物之后，重量和最大的一堆货物重量是多少？
输入第一行包含一个正整数n，表示货物的数量。(1<=n,m<=50000) 输入第二行包含n个正整数，表示1~n号货物的重量w_i。(1<=w_i<=100) 输入第三行有n个数，表示小美按顺序取出的货物的编号，也就是一个1~n的全排列。
输出包含n行，每行一个整数，表示每取出一件货物以后，对于重量和最大的一堆货物，其重量和为多少。
5 3 2 4 4 5 4 3 5 2 1
9 5 5 3 0
考点：并查集
数据规模 n ≤ 50000 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出
推荐方向：并查集
本题切入点
取货会把一堆切开（等价于删点），正序难维护；把取货顺序倒过来就变成不断地「加入节点并合并左右两堆」，用并查集 + 堆维护最大堆和。
用「代表元」高效维护集合合并与连通性查询，均摊近 O(1)。
思路框架（并查集 通法 · 非本题专属）
实现要点：路径压缩 + 按大小合并，复杂度近似 O(α(n))。
复杂度：时间 O(n α(n)) ｜ 空间 O(n)
该范式的通法易错点
对照本题
样例 1：输入 5 / 3 2 4 4 5 / 4 3 5 2 1 → 输出 9 / 5 / 5 / 3 / 0
原本的状态是{{3,2,4,4,5}}，取出4号货物后，得到{{3,2,4},{5}}，第一堆货物的和是9，,然后取出3号货物得到{{3,2}{5}}，此时第一堆和第二堆的和都是5，以此类推
解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。
本题来源：美团2023校招技术第3场编程题。