27878번 - 순열 사이클과 쿼리 서브태스크

\(1\)이상 \(n\)이하의 서로 다른 정수 \(n\)개로 이루어진 배열 \(A\)와 정수 \(m\)이 주어진다. \(S^0(i)=i,\ S^k(i)=A[S^{k-1}(i)]\ (1\ \le\ k\ \le\ m,\ 1\ \le\ i\ \le\ n)\) 로 정의하자. \(S^m(i)\)에 대한 \(q\)개의 질의가 저장된 질의 목록 \(Q\)가 주어진다. 질의 목록 \(Q\)에 저장된 \(q\)개의 질의는 아래 두 가지 유형으로 구분된다. 첫 번째가 유형 \(1\), 두 번째가 유형 \(2\)를 나타낸다.

• \(1\ i\ j\) : \(A[i]\)와 \(A[j]\)의 값을 교환한다.
• \(2\) : \(S^m(1)×1\,+\,S^m(2)×2\,+\,...\,+\,S^m(n)×n\) 값을 출력한다.

질의 목록 \(Q\)에 저장된 첫 번째 질의부터 \(q\)번째 질의까지 순서대로 처리하면서 유형 \(2\)의 질의 결과를 출력하자.

첫 번째 줄에 \(n\)과 \(m\)이 공백을 사이에 두고 순서대로 주어진다.

두 번째 줄에 배열 \(A\)의 원소 \(A[1],\ A[2],\ ...,\ A[n]\)이 공백을 사이에 두고 순서대로 주어진다.

세 번째 줄에 질의의 수 \(q\)가 주어진다.

네 번째 줄부터 \(q\)개의 줄에 걸쳐 질의 목록 \(Q\)에 저장된 \(q\)개의 질의가 순서대로 주어진다. 한 줄에 하나의 질의를 나타내는 정수가 공백을 사이에 두고 순서대로 주어진다.

첫 번째 줄부터 유형 \(2\)의 질의 결과를 순서대로 한 줄씩 출력한다.

• \(1\ \le\ n,\ q\ \le 100,000\)
• \(1\ \le\ m\ \le\ 10^{1,000}-1\)
• \(1\ \le\ A[i]\ ≠\ A[j]\ \le\ n\ (1\ \le\ i\ ≠\ j\ \le\ n)\)
• 질의 목록 \(Q\)에 저장된 질의는 유형 \(1\), 유형 \(2\)만 존재한다.
• 질의 목록 \(Q\)에는 유형 \(2\)의 질의가 \(1\)개 이상 \(min(q,\ 1,000)\)개 이하 저장되어 있다.

\(S^m\)은 배열 \(A\)의 원소를 이동시키는 이동 연산을 \(m\)번 반복하는 동작이다. \(i\)번째\((1\ \le\ i\ \le\ n)\) 원소에 이동 연산을 \(k\)번\((0\ \le\ k\ \le\ m)\) 수행한 후, \(i\)번째 원소의 위치를 \(S^k(i)\)라고 하자. 즉, \(i\)번째 원소의 초기 위치는 \(S^0(i)=i\), 1번 이동시킨 후 위치는 \(S^1(i)=A[i]\), 2번 이동시킨 후 위치는 \(S^2(i)=A[S^1(i)]\), ..., \(m\)번 이동시킨 후 위치는 \(S^m(i)=A[S^{m-1}(i)]\)이다. 예를 들어, 배열 \(A=\{2,\ 1,\ 3\}\)이고 \(m=3\)이라고 하자. 첫 번째 원소에 대한 이동은 \(S^0(1)=1,\ S^1(1)=A[1]=2,\ S^2(1)=A[S^1(1)]=1,\ S^3(1)=A[S^2(1)]=2\)이다. 두 번째 원소에 대한 이동은 \(S^0(2)=2,\ S^1(2)=A[2]=1,\ S^2(2)=A[S^1(2)]=2,\ S^3(2)=A[S^2(2)]=1\)이다. 세 번째 원소에 대한 이동은 \(S^0(3)=3,\ S^1(3)=A[3]=3,\ S^2(3)=A[S^1(3)]=3,\ S^3(3)=A[S^2(3)]=3\)이다.