Pivots

https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day3/problems/B

I found an interesting solution. Most of the solutions use a linked list, but it is based on another property. The operation LxR->RxL is similar to LR->RL. LR->RL is well-known as rotation (C++ standard library contains it). Then, consider the following problem.

Given a permutation with N elements and Q queries. Each query is in the following form.

• Given k, rotate k elements. That is, change a[0],...,a[k-1],a[k],...,a[n-1] to a[k],...,a[n-1],a[0],...,a[k-1].

Please print the permutation after all queries are performed. This problem is really easy because just trace the beginning position. Actually, the original problem can also be solved by a similar technique.
That is why LxR->RxL can be treated as a rotation. Appending x to the end, it becomes LxRx -> RxLx.

#include <stdio.h>

int a[100001];
int pos[100000];

int main() {
  int n, q;
  scanf("%d %d", &n, &q);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    a[i]--;
    pos[a[i]] = i;
  }
  int k = n;
  while (q--) {
    int b;
    scanf("%d", &b);
    b--;
    a[k] = b;
    int tmp = pos[b];
    pos[b] = k;
    k = tmp;
  }
  for (int i = 0; i < n; i++) {
    if (i) putchar(' ');
    printf("%d", a[(i + k + 1) % (n + 1)] + 1);
  }
  putchar('\n');
}