Courses

數據結構

笛卡尔树

Module: 笛卡尔树

Problem

3 /3

购物车分类

Problem

<分区> <分区> U Akaki 是一副 n 张牌。每张卡片上都写着一个从 1 到 100 000 的整数。有些卡片上可能写着相同的数字。

<分区> 赤木决定对牌组中的所有牌进行排序。为此，他轮流从牌堆中取出一张顶牌，如果写在上面的数字等于牌堆中所有剩余数字中的最小值，他将这张牌放在一边。否则，赤木将这张牌放在牌堆底，然后从牌堆顶抽下一张牌。当牌组中没有牌时，该过程结束。我们可以假设 Akaki 在任何时候都知道写在牌组中一些剩余牌上的最小数量，但不知道这张牌（或多张牌）在牌组中的位置。

<分区> 你的任务是确定 Akaki 查看牌组顶牌的总次数。

<分区>

<分区> 输入

<分区> 第一行后面跟着一个正整数n(1 ≤ n ≤ 100 000)—一副牌中的牌数。

<分区> 第二行包含 n 个正整数序列 a₁, a₂, ..., a_n ( 1 ≤ a_i ≤ 100 000), 其中 a_i 等于写在第 i 个顶牌上的数字甲板。< /div> <分区>

<分区> 输出

<分区>

<分区> 打印 Akaki 查看牌组顶牌的总次数。

<正文>

<分区> 注意 <分区> 在第一个例子中，Akaki 会先看数字为 6 的牌，将其放在牌组的底部，然后是数字为 3 的牌，也放在牌组的底部，然后是数字为 3 的牌。数字 1。他将把数字为 1 的卡片放在一边，因为它包含了甲板上剩余的最小数字。之后，牌组中的牌将从上到下排列为 [2, 6, 3]。之后，赤木会看最上面的数字为2的牌，并把它放在一边。之后，牌组中的牌将从上到下排列 [6, 3] 的顺序。然后 Akaki 将查看数字为 6 的卡，将其放在牌组底部，然后是数字为 3 的卡，他将其放在一边。之后，牌组中将保留一张编号为 6 的牌，赤木将查看并放在一边。因此，Akaki 将查看 7 张牌。 <分区> <分区> (c) Kurbatov E., 2018

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking