J  Worldwide Playlist

Observe that the number of skips is equal to the number of songs played minus \(n\).

To listen to the songs \(b_1, \ldots, b_n\) in order, the total number of songs played is equal to \(\operatorname{pos}_a(b_n) + kn\), where \(\operatorname{pos}_a(x)\) denotes the position of song \(x\) in the permutation \(a\), and \(k\) is the number of wraps around the playlist: the number of times \(a_1\) is played after \(a_n\).

We can see that a wrap occurs whenever the next desired song appears earlier in the permutation \(a\) than the current song. In other words, \(k\) is equal to the number of indices \(i\) such that \(\operatorname{pos}_a(b_{i+1}) \lt \operatorname{pos}_a(b_i)\).

Next, let us handle updates. We maintain an array storing \(\operatorname{pos}_a(i)\) for \(1 \le i \le n\).

• To handle updates with \(c = 2\), since swapping \(b_x\) and \(b_y\) affects only the comparisons involving these two positions, we can update the corresponding contributions to \(k\) in \(O(1)\).
• To handle updates with \(c = 1\), note that swapping \(a_x\) and \(a_y\) changes \(\operatorname{pos}_a(i)\) for two values of \(i\). We can recompute their contributions to \(k\) in \(O(1)\) as well.

Therefore, the total time complexity is \(O(n + q)\).