Worldwide Playlist

Research checked: the official Codeforces statement at https://codeforces.com/problemset/problem/2206/J and the official tutorial PDF at https://codeforces.com/contest/2206/attachments/download/36244/analysis.pdf. The tutorial's core observation is the wrap-count formula; the explanation below expands the proof and update mechanics.

Let

$p_i = \operatorname{pos}_a(b_i),$

where $\operatorname{pos}_a(x)$ is the current position of song $x$ inside playlist permutation $a$.

After this conversion, the actual song labels stop mattering. We only need to listen to positions

$p_1,p_2,\ldots,p_n$

in this order while walking forward around a cyclic array of length $n$.

Suppose we just listened to $b_i$, currently at position $p_i$ in $a$.

• If $p_{i+1}>p_i$, then $b_{i+1}$ is still ahead in the same cycle.
• If $p_{i+1}<p_i$, then we must pass the end of the playlist and wrap back to $a_1$.

Since $b$ is a permutation, equal positions never happen for adjacent songs. No sneaky tie case, thank god.

Define

$k = \#\{i \mid 1 \le i < n,\ p_i > p_{i+1}\}.$

This $k$ is exactly the number of wraps before finishing all desired songs.

Now compute the total number of playlist entries encountered. If there were no cyclic wrapping, ending at position $p_n$ would mean exactly $p_n$ entries from the start. Each wrap adds one full extra cycle of $n$ entries. Therefore:

$\text{played} = p_n + k n.$

Exactly $n$ of those entries are listened to in full, one for each desired song. Everything else is skipped, so

$\text{answer} = p_n + k n - n.$

That is the whole math. The rest is just not botching the updates.

Maintain:

• a[pos]: song at position pos in playlist $a$,
• whereA[song]: current $\operatorname{pos}_a(song)$,
• b[i]: desired song at index i,
• whereB[song]: current position of song inside $b$,
• bad[i] for $1 \le i < n$:

$bad[i] = [\operatorname{pos}_a(b_i) > \operatorname{pos}_a(b_{i+1})].$

Then

$k = \sum_{i=1}^{n-1} bad[i].$

So the current answer is

$\operatorname{pos}_a(b_n) + k n - n.$

Updating $b$

If we swap $b_x$ and $b_y$, only adjacent comparisons touching indices $x$ or $y$ can change:

$x-1,\,x,\,y-1,\,y.$

We remove their old contributions, swap the two values, update whereB, then add their new contributions.

Updating $a$

If we swap $a_x$ and $a_y$, the only songs whose $\operatorname{pos}_a$ values change are those two songs:

$s_1=a_x,\quad s_2=a_y.$

A changed song position can only affect descent comparisons where that song appears in $b$, so again only constant many indices matter:

$whereB[s_1]-1,\ whereB[s_1],\ whereB[s_2]-1,\ whereB[s_2].$

Remove those contributions, swap the songs in a, update whereA, then add contributions back.

Use a tiny list of candidate indices and deduplicate it, because when $x$ and $y$ are close, the same bad[i] can appear twice. Double-removing a contribution is the kind of bug that makes you question free will.

Proof of Correctness

We prove that the algorithm outputs the minimum number of skips for every day.

First, for fixed permutations $a$ and $b$, consider $p_i=\operatorname{pos}_a(b_i)$. Starting from $a_1$, to hear $b_1$ first, every playlist entry before position $p_1$ must be skipped, and listening to $b_1$ consumes position $p_1$. There is no alternative route because the playlist order is fixed and only moves forward.

For every transition from $b_i$ to $b_{i+1}$, the next listened song must be the first future occurrence of $b_{i+1}$ in the infinite playlist. If $p_{i+1}>p_i$, that occurrence is in the same cycle; otherwise it is in the next cycle. Thus a wrap happens exactly when $p_i>p_{i+1}$.

After all transitions, the final listened song is at position $p_n$ in the current cycle, plus one full cycle for each wrap. Therefore the total number of playlist entries encountered is exactly

$p_n + n\cdot \#\{i:p_i>p_{i+1}\}.$

Among these entries, exactly $n$ are listened to fully. Every other encountered entry must have been skipped, and skipping fewer is impossible because those entries occur before the next required full song. Hence the minimum number of skips is

$p_n + kn - n.$

Now for updates. The value $k$ depends only on adjacent comparisons

$\operatorname{pos}_a(b_i)>\operatorname{pos}_a(b_{i+1}).$

Swapping two entries of $b$ changes only comparisons adjacent to the swapped indices, so recomputing those indicators preserves the exact sum $k$. Swapping two entries of $a$ changes only the positions of the two swapped songs; a descent indicator can change only if one of those songs is one of its two endpoints in $b$, so recomputing the indicators adjacent to their positions in $b$ also preserves the exact sum $k$.

Thus after every update, the maintained $k$ is correct, and by the formula above the printed answer is correct.

Complexity

Initialization is $O(n)$. Each update touches $O(1)$ candidate descent positions, so each day is processed in $O(1)$ time.

Total complexity:

$O(n+d)$

with $O(n)$ memory.