Lost Civilization (Hard Version)

Research checked: the official Codeforces problem page, the contest editorial page, and kmjp's write-up. The statement is the source of truth here.

First solve the easy question: what is $f(b)$ for one sequence $b$?

Think of the insertion process as building a rooted forest. Every original input element is a root. When we insert $x+1$ immediately after an existing $x$, we create a child of that $x$. The final sequence is a preorder traversal of this forest, and every edge increases the value by exactly $1$.

Now scan a candidate sequence from left to right. At any moment, the only previous elements that can still receive the next node are the active ancestors on the current preorder path. Since every edge adds $1$, their values form a consecutive interval:

$$[L,R].$$

For the next value $v$:

• if $v-1 \in [L,R]$, then $v$ can be attached under that active ancestor, so it is not a new original element;
• otherwise, no active parent exists, so $v$ must start a new root. No amount of wishful thinking fixes that. A dead earlier $v-1$ is dead.

After processing $v$, the top of the active path has value $v$, so $R=v$. If $v$ started a new root, then the whole old path is gone and $L=v$ too. Otherwise $L$ stays the same.

So for one sequence:

$$f(b)=\#\{\text{positions where } b_i-1 \notin [L,R]\text{ before processing }b_i\}.$$

Now move to the hard version. Instead of recomputing this for every subsegment, count each position's contribution.

Fix an index $i$. Let $c_i$ be the number of left endpoints $l \le i$ such that, when scanning $a_l,a_{l+1},\ldots,a_i$, the element $a_i$ starts a new root. Once $l$ and $i$ are fixed, the right endpoint can be any $r \ge i$, so position $i$ contributes

$$c_i(n-i+1)$$

to the answer.

We just need $c_i$ fast.

Maintain the active interval $[L,R]$ for the full prefix $a_1,\ldots,a_{i-1}$, using the one-sequence scan above. Also maintain last[x], the latest position where value $x$ appeared.

Let

$$need=a_i-1.$$

There are two cases.

If $need \notin [L,R]$, then $need$ is not active even when starting from $1$. Starting later cannot magically make an inactive missing parent appear before $i$. Therefore every left endpoint $1,2,\ldots,i$ makes $a_i$ a new root:

$$c_i=i.$$

Then $a_i$ is a new root in the full prefix too, so set $L=a_i$.

If $need \in [L,R]$, then the active node with value $need$ must be the latest occurrence of that value. Let its position be

$$p=last[need].$$

For every $l \le p$, that occurrence is included and remains active before $i$, so $a_i$ is generated. For every $l>p$, that occurrence is excluded, and there is no later $need$, so $a_i$ must be a new root. Thus

$$c_i=i-p.$$

In both cases, after processing $a_i$, set $R=a_i$ and update last[a_i]=i.

The answer is

$$\sum_{i=1}^{n} c_i(n-i+1).$$

A couple of edge cases are worth calling out:

• If $a_i=1$, then $need=0$, which can never be active because all values are positive, so all starts pay.
• Equal adjacent values do not generate each other. You need $v-1$, not $v$.
• Large jumps and decreases are naturally handled by the interval test.

The implementation below uses coordinate compression for last, avoiding hash-table nonsense. Complexity is $O(n\log n)$ per test case from sorting and binary searches, with $O(n)$ memory. Since $\sum n \le 300000$, this is comfortably accepted.