Counting Cute Arrays

Catalan Skeleton

Look at the last element of a cute array $P=f(A)$. Let $P_n=p$.

If $p>0$, then by definition

$$A_p<A_n\le A_{p+1},A_{p+2},\ldots,A_{n-1}.$$

So every index in the right block $p+1,\ldots,n-1$ has $p$ as a smaller element before it. Its parent label is therefore at least $p$. After subtracting $p$, this right block becomes a smaller cute array, where global parent $p$ becomes local $0$.

The prefix $1,\ldots,p$ is also independent. Thus the key recurrence is:

$$P\text{ is cute}\iff P_n=p,\quad P[1..p]\text{ is cute},\quad (P_{p+1}-p,\ldots,P_{n-1}-p)\text{ is cute}.$$

The converse works by shifting values in the right block upward and choosing $A_n$ between $A_p$ and all right-block values. For $p=0$, choose $A_n$ below everything before it. No wizardry, just inequalities doing their job.

This is exactly the Catalan recurrence. More usefully, it gives an online stack process:

• Start with stack $[0]$.
• For $i=1,2,\ldots,n$, choose $P_i$ from the current stack.
• Pop everything above $P_i$.
• Push $i$.

A sequence $P$ is cute if and only if it can be produced by this process. Think of it as preorder labels of a rooted ordered tree. Catalan objects wearing a fake mustache.

Fixed Values

If $X_i\ne -1$, then at time $i$ we are forced to choose stack element $X_i$.

First, $X_i<i$ must hold. Otherwise $i$ is trying to use itself or the future as a parent, which is nonsense.

Second, two fixed choices cannot cross. For fixed $i<j$, if

$$X_i<X_j<i,$$

then at time $i$ choosing $X_i$ pops every active vertex above $X_i$. The already-created vertex $X_j$ lies above $X_i$, so after time $i$ it is gone from the stack forever. Then time $j$ can never choose $X_j$. Dead.

So any such pair makes the answer $0$.

Compressing Forced Edges

Write a fixed choice $X_v=u$ as a forced edge $u\to v$. Process all forced edges in increasing order of length $v-u$.

Maintain jump[u]. If jump[u]=v, it means the already-processed part from $u$ up to $v$ has been compressed into one forced push $u\to v$ for future, larger segments.

For a fixed edge $u\to v$:

1. Count all still-free choices in the segment from $u$ through $v-1$ by calling calc(u, v-1).
2. Then compress the forced edge by setting jump[u]=v.

If jump[u] already existed, overwriting is intentional: that older compressed block has just been included inside the new larger block.

After all fixed edges are processed, call calc(0,n) using the artificial root $0$.

The no-crossing check guarantees that when we process $u\to v$, every fixed edge that can affect the inside of this segment has smaller length and was already compressed. That is the whole trick. Without it, this would be cubic garbage.

The DP Inside calc(l,r)

During calc(l,r), we scan forward from the current vertex cur. The segment start $l$ is already on the stack.

Let $dp[d]$ be the number of ways after scanning to cur, where cur has relative depth $d$ from the segment start. Depth $d$ means there are $d+1$ available stack vertices inside this segment.

Initially:

$$dp[0]=1.$$

There are two transitions.

If jump[cur] exists, the next vertex is forced to be a child of cur. So the depth simply increases:

$$dp'_{d+1}=dp_d.$$

Otherwise, the next raw vertex is free. From old depth $d$, it may attach to any ancestor at depth $0,1,\ldots,d$. If it attaches to depth $q$, the new depth is $q+1$. Therefore

$$dp'_k=\sum_{d\ge k-1} dp_d\quad(k\ge 1),\qquad dp'_0=0.$$

This transition is just suffix sums. At the end of the segment, any depth is acceptable, so multiply the global answer by

$$\sum_d dp[d].$$

Complexity

The crossing check costs $O(n^2)$. The compressed segment DP also costs $O(n^2)$ total over one test case: each compressed layer is expanded only when it is created, and later it is followed as one forced jump. Memory is $O(n)$.

With $\sum n\le 5000$, this is comfortably within limits.

Reference checked for verification: official Codeforces editorial.