Inversion Graph Coloring (Hard Version)

The key is to stop thinking about colors first. Colors are just the symptom. The actual disease is a decreasing triple.

From Coloring To Decreasing Triples

Take any selected subsequence $b$.

If it contains indices $i<j<k$ with

$$b_i>b_j>b_k,$$

then all three pairs are inversions, so the inversion graph contains a triangle. A triangle cannot be 2-colored, so the subsequence is not good.

Now the less obvious direction: if there is no decreasing subsequence of length $3$, then the inversion graph is bipartite.

Classify each selected element by the length of the longest decreasing subsequence ending there. Since length $3$ never happens, every selected element has rank either $1$ or $2$.

Elements of the same rank cannot form an inversion:

• If two rank-$1$ elements formed a decreasing pair, the later one would have rank at least $2$.
• If two rank-$2$ elements formed a decreasing pair, take the earlier rank-$2$ element's previous bigger element. Together they form a decreasing triple. Boom, illegal.

So each rank class is nondecreasing, meaning every inversion goes between the two classes. Color rank $1$ red and rank $2$ blue. Done.

Therefore:

$$\text{good subsequence} \iff \text{no strictly decreasing subsequence of length }3.$$

That is the whole graph part. The graph has left the building.

Compress Values Without Breaking Inversions

The array can have equal values. Inversions are strict, so equal values must not become inversions accidentally.

Replace each $a_i$ by its stable rank among pairs $(a_i,i)$ sorted increasingly. Equivalently:

$$r_i = 1 + |\{j<i : a_j\le a_i\}| + |\{j>i : a_j<a_i\}|.$$

This creates a permutation of $1,2,\dots,n$.

For every $i<j$:

$$a_i>a_j \iff r_i>r_j.$$

Equal original values get increasing ranks by index, so they still do not create inversions. Nice and clean.

From now on, assume the sequence is a permutation.

DP State

Process positions from left to right.

For every good selected subsequence inside the processed prefix, store:

• $j$: the maximum selected value,
• $q$: the maximum selected value that has some bigger selected value before it.

If no such value exists, $q=0$. The empty subsequence is state $(0,0)$.

Why does $q$ matter? Because every future selected value below $q$ would complete a decreasing triple.

Suppose a previous value $q$ already had a bigger value before it. If we now choose $x<q$, then we have

$$\text{bigger value} > q > x,$$

in increasing index order. That is exactly the forbidden triple. So future chosen values that are not new maxima must stay above $q$.

Transitions

Let the next value be $x$.

We can always skip it.

If we take it, there are two cases.

Case 1: $x>j$.

Then $x$ is bigger than everything selected so far, so it is not preceded by a bigger value. The new state is:

$$(j,q) \to (x,q).$$

Case 2: $x<j$.

Then the old maximum $j$ is before $x$ and bigger than $x$, so $x$ is now a value preceded by a bigger one. This is valid only if $x>q$. The new state is:

$$(j,q) \to (j,x).$$

If $x<j$ but $x\le q$, taking $x$ creates a decreasing triple, so nope.

The naive DP is:

$$dp[j][q] = \#\text{ways to reach state }(j,q).$$

For each $x$, the updates are:

$$dp[j][x] \mathrel{+}= \sum_{q<x} dp[j][q] \quad \text{for all } j>x,$$

and

$$dp[x][q] \mathrel{+}= \sum_{j<x} dp[j][q] \quad \text{for all } q<x.$$

These formulas already include the skip transition implicitly, because we never delete old states.

Speeding It Up

There are $O(n^2)$ states. For each element, we need many prefix sums:

• row prefix sums: $\sum_{q<x} dp[j][q]$,
• column prefix sums: $\sum_{j<x} dp[j][q]$.

Use Fenwick trees:

• one Fenwick tree per row $j$,
• one Fenwick tree per column $q$.

When we add some value to $dp[j][q]$, update both structures.

For a value $x$:

• For every $j>x$, compute $\sum_{q<x} dp[j][q]$ from row $j$ and add it to state $(j,x)$.
• For every $q<x$, compute $\sum_{j<x} dp[j][q]$ from column $q$ and add it to state $(x,q)$.

Important: buffer all updates for the current $x$ first, then apply them. Otherwise the same array element could be used twice in one transition, which would be cursed and wrong.

Finally, sum all states. State $(0,0)$ is included, so the empty subsequence is counted automatically.

Complexity

For each of $n$ elements, we do $O(n)$ Fenwick queries/updates, each costing $O(\log n)$.

$$O(n^2\log n)$$

Memory is $O(n^2)$, which is fine for $n\le 2000$.