Official

G - Swap Many Times Editorial by en_translator


Let’s group the \(L\)-th through \(R\)-th integer pairs \((l, r)\) in the lexicographical order by the values of \(l\):

  • \((a, b), \dots, (a, N)\)
  • \((a+1, a+2), \dots, (a, N)\)

\(\qquad \vdots\)

  • \((a+k, a+k+ 1), \dots, (a+k, N)\)
  • \((a+k+1, a+k+2), \dots, (a+k+1, c)\)

For example, when \(N = 6, L = 3\), and \(R = 13\), we can paint the \(L\)-th, \(\dots\), \(R\)-th (lexicographically) smallest integer pairs as follows. Here, if \((l, i)\) should be colored for all \(l + 1 \leq i \leq N\), then the \(l\)-th row is painted red; otherwise, they are painted blue.

The number of integer pairs painted blue is \(O(N)\). We can process them naively within the time limit.

On the other hand, there are at most \(\Theta (N^2)\) integer pairs painted red, so we cannot process them naively. Instead, let focus on what will happen to the sequence when we perform all the operations corresponding to the pairs in a column.

For a sequence \((1, 2, \dots, N)\), if you perform the operations corresponding to \((1, i)\) for all \(i=2, \dots, N\) in this order, it will result in \(n = 1, \dots, k\). Therefore, it can be achieved by the following operation:

  • Pop the last element from the sequence and insert it at the position right before the \((a+n)\)-th term.

Here is an example of operations.

Therefore, performing all the operations corresponding to pairs painted red is equivalent to reversing \(A_{a+1} \dots, A_N\) and then reversing \(A_{a+k+1}, \dots, A_N\) again.

Hence, the problem can be solved in a total of \(O(N)\) time by performing the following steps.

  • Find the values of \(a, b, k, c\). If \(l = a\) for all pairs \((l, r)\) to be processed, then do the process naively and ignore the remaining steps.
  • Perform the operations for \((a, b), \dots, (a, N)\) naively.
  • Reverse \(A_{a+1} \dots, A_N\) and reverse \(A_{a+k+1}, \dots, A_N\) again.
  • Perform the operations for \((a + k + 1, a + k + 2), \dots, (a+k+1, c)\) naively.

Sample code (C++)

posted:
last update: