# 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');
}