Prefix Maximum Invariance

First, shrink the scary definition until it stops acting tough.

For one fixed pair of arrays $x,y$, let

$P_i=\max(x_1,\ldots,x_i).$

The condition on $z$ is exactly that the prefix maximum sequence of $z$ is $P$.

At position $i$:

• always $z_i\le P_i$, otherwise the prefix maximum becomes too large;
• if $P_i>P_{i-1}$, then $z_i$ is forced to be $P_i$, because this position is the one that creates the new prefix maximum;
• if $P_i=P_{i-1}$, then $z_i$ can be any integer $\le P_i$.

So for a fixed subarray $[l,r]$, position $i$ can be matched with $b_i$ iff one of these happens:

1. $a_i$ is a strict prefix maximum inside $a_l,\ldots,a_i$, and $b_i=a_i$.
2. $a_i$ is not a strict prefix maximum inside $a_l,\ldots,a_i$, and $b_i\le \max(a_l,\ldots,a_i)$.

That is the key deconstruction. There is no global DP over $z$. Each position either can be made equal to $b_i$ or it cannot. Nice.

Turning the double sum around

Instead of iterating over every subarray, count how many subarrays each position $i$ contributes to.

A contribution of position $i$ depends only on the left endpoint $l$ and the prefix $a_l,\ldots,a_i$. Once $l$ and $i$ are fixed, every right endpoint $r\ge i$ includes that same contribution.

So if $c_i$ is the number of left endpoints $l\le i$ for which position $i$ is matchable, then the answer is

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

Now we only need to compute each $c_i$.

When is $a_i$ a strict prefix maximum?

Let

$p_i=\max\{j<i: a_j\ge a_i\},$

or $0$ if no such index exists.

Then $a_i$ is a strict maximum of $a_l,\ldots,a_i$ exactly when no earlier element in that range is $\ge a_i$. That means

$l>p_i.$

So the strict-prefix-maximum left endpoints are

$l\in[p_i+1,i].$

There are $i-p_i$ of them.

If $b_i=a_i$, all of those left endpoints are valid.

If $b_i\ne a_i$, none of those strict endpoints are valid, because $z_i$ is forced to equal $a_i$. No negotiating with the prefix maximum police.

The non-strict case

Now consider left endpoints where $a_i$ is not a strict prefix maximum. These are exactly

$l\le p_i.$

For these, the current prefix maximum is

$M=\max(a_l,\ldots,a_i),$

and position $i$ can match iff

$b_i\le M.$

Because $a_i$ is not strict here, $M\ge a_i$. If $b_i\le a_i$, then automatically $b_i\le M$, so every $l\le p_i$ works.

If $b_i>a_i$, then we need some previous element in $[l,i-1]$ that is at least $b_i$.

Define

$q_i=\max\{j<i:a_j\ge b_i\},$

or $0$ if no such index exists.

Then there is such an element in $[l,i-1]$ exactly when

$l\le q_i.$

So the number of valid non-strict left endpoints is:

• $p_i$ if $b_i\le a_i$;
• $q_i$ if $b_i>a_i$.

Notice that when $b_i>a_i$, any index with $a_j\ge b_i$ also has $a_j\ge a_i$, so $q_i\le p_i$. Good, no hidden overcount.

Final formula

For each position $i$:

• strict part: contributes $i-p_i$ only if $b_i=a_i$;
• non-strict part:
  • contributes $p_i$ if $b_i\le a_i$;
  • contributes $q_i$ if $b_i>a_i$.

So

\begin{cases} i, & b_i=a_i,\\ p_i, & b_i<a_i,\\ q_i, & b_i>a_i. \end{cases}$$ Why does $b_i=a_i$ become $i$? Because the strict part gives $i-p_i$, and the non-strict part gives $p_i$, so every left endpoint works. If $b_i=a_i$, just set $z_i=a_i; of course it fits. Then add $$c_i(n-i+1)$$ to the answer. **Computing $p_i$ and $q_i$** We need previous indices with values at least some threshold. For $p_i$, the threshold is $a_i$. For $q_i$, the threshold is $b_i$. Since $a_i,b_i\le 2n$, this can be done with a Fenwick tree over values. Sweep $i$ from left to right. The Fenwick tree stores, for each value $v$, the maximum index seen so far with $a_j=v$. To query the maximum previous index with value at least $T$, query the suffix $[T,2n]$. A standard Fenwick tree does prefix queries, so flip the value: $$rev(v)=V-v+1,$$ where $V=2n+2$. Then values $\ge T$ become reversed indices $\le rev(T)$, so a prefix maximum query gives exactly what we want. After answering queries for position $i$, insert $a_i$ with value $i$. Complexity: $O(n\log n)$ per test case, and $O(n)$ memory. With total $n\le 2\cdot 10^5$, this is comfortably AC.