← 返回题目列表

Codeforces · 1290/E

E. 笛卡尔树

中文机器翻译题面 查看原题

Ildar是William和Harris的算法老师。今天,伊尔达正在教授笛卡尔树。然而,哈里斯生病了,所以伊尔达只教威廉。

笛卡尔树是一棵有根树,可以由一系列不同的整数构成。我们按如下方式构建笛卡尔树:

1.如果序列为空,则返回空树;
2、设最大元素的位置为$$$x$$$;
3.从序列中删除$$$x$$$位置上的元素,并将其分成左右部分(可能是空的)(不是真正删除,只是暂时拿走);
4.为每个部分构建笛卡尔树;
5. 为元素创建一个新顶点,该顶点位于 $$$x$$$ 位置,它将作为新树的根。然后,对于左部分和右部分的根,如果存在,将成为该顶点的子节点;
6. 返回我们得到的树。

例如,这是序列 $$$4, 2, 7, 3, 5, 6, 1$$$ 的笛卡尔树:

教完笛卡尔树是什么后,Ildar 布置了作业。他从一个空序列 $$$a$$$ 开始。

在第 $$$i$$$ 轮中,他在 $$$a$$$ 中的某处插入了一个值为 $$$i$$$ 的元素。然后,他提出一个问题:当前序列 $$$a$$$ 的笛卡尔树中每个节点的子树大小之和是多少?

节点 $$$v$$$ 位于节点 $$$u$$$ 子树中当且仅当 $$$v = u$$$ 或 $$$v$$$ 位于节点 $$$u$$$ 子节点之一的子树中。节点$$$u$$$的子树的大小是使得$$$v$$$位于$$$u$$$的子树中的节点$$$v$$$的数量。

Ildar 总共将进行 $$$n$$$ 轮。家庭作业是对 $$$n$$$ 问题的回答序列。

第二天,伊尔达告诉哈里斯他也必须完成作业。哈里斯从威廉那里获得了序列 $$$a$$$ 的最终状态。然而,他不知道如何找到 $$$n$$$ 问题的答案。帮助哈里斯!

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 150000$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$)。保证从 $$$1$$$ 到 $$$n$$$ 的每个整数在序列中只出现一次。

输出

打印 $$$n$$$ 行,第 $$$i$$$ 行应包含一个整数 - 第 $$$i$$$ 问题的答案。

示例

输入 #1

5
2 4 1 5 3

输出 #1

1
3
6
8
11

输入 #2

6
1 2 4 5 6 3

输出 #2

1
3
6
8
12
17

注意

第一轮结束后,顺序是$$$1$$$。这棵树是

答案是$$$1$$$。

第二轮结束后,顺序是$$$2, 1$$$。这棵树是

答案是$$$2+1=3$$$。

第三轮结束后,顺序是$$$2, 1, 3$$$。这棵树是

答案是$$$2+1+3=6$$$。

第四轮结束后,顺序是$$$2, 4, 1, 3$$$。这棵树是

答案是$$$1+4+1+2=8$$$。

第五轮结束后,顺序是$$$2, 4, 1, 5, 3$$$。这棵树是

答案是$$$1+3+1+5+1=11$$$。