Good Schedule

Observation 1

For one person, the set of watched episodes is always a prefix. If they have watched $1,2,\dots,x-1$, then on a day with value $c_i$ they watch exactly when $c_i=x$.

So while Alice and Bob have the same next needed episode $x$, a day is legal iff either both values are $x$, or neither value is $x$.

A valid segment never lets their progress differ. Starting equal, they either both advance by watching episode $x$, or both do nothing.

Observation 2

Fix a moment just after day $t$, and suppose the next needed episode is $x$. Every future day that does not contain $x$ is pure noise. The first future day containing $x$ decides everything:

$$q=\min\{i>t : a_i=x \text{ or } b_i=x\}.$$

If no such $q$ exists, nothing bad can ever happen. If $a_q=b_q=x$, they both watch episode $x$ and the state becomes $x+1$ after day $q$. Otherwise exactly one side sees episode $x$, and the segment dies at $q$. Brutal, but convenient.

Events

For each episode $x$, store all days where $x$ appears in either schedule. Mark a stored day as:

• good if $a_i=b_i=x$;
• bad if exactly one of $a_i,b_i$ equals $x$.

If $a_i \ne b_i$, the same day is a bad event for both values $a_i$ and $b_i$.

DP

For a good event at day $p$ for episode $x$, define $dp[p]$ as the first bad day after they have just watched episode $x$ on day $p$. Equivalently, the next needed episode is $x+1$ after $p$.

To compute it, look in the event list of episode $x+1$ for the first event after $p$:

$$q=\min\{i>p : a_i=x+1 \text{ or } b_i=x+1\}.$$

• If $q$ does not exist, $dp[p]=n+1$.
• If $q$ is bad for $x+1$, then $dp[p]=q$.
• If $q$ is good for $x+1$, then $dp[p]=dp[q]$.

This is why we process episodes in decreasing order: when computing episode $x$, all dp values for good events of episode $x+1$ are already known. No magic, just refusing to do the same simulation $n$ times.

Counting

For a left endpoint $L$, the first relevant event is the first event of episode $1$ at day $q \ge L$.

• If it does not exist, every $R\in[L,n]$ works.
• If it is bad, the first invalid day is $q$.
• If it is good, the first invalid day is $dp[q]$.

Let this first invalid day be $bad(L)$, using $n+1$ if there is none. Then exactly

$$bad(L)-L$$

segments start at $L$. Sum this over all $L$.

Each event list is binary-searched a constant number of times. There are at most $2n$ stored events, so the complexity per test case is

$$O(n\log n)$$

with $O(n)$ memory. The constraints are fine; no need for a cursed quadratic simulator.