페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#4721

가지치기 4s 1024MB

문제

양의 정수 n과 양의 정수로 이루어진 수열 a1, ... , an이 주어진다.

이때 ai는 {{i\times(i-1)}\over 2} < a_i\leq {{i\times(i+1)}\over 2} 를 만족한다.

이 수열은 {(n+1)\times(n+2)}\over2개의 정점으로 이루어진 트리를 표현한다.

구체적으로 이 트리는 깊이 i인 정점이 i개씩 깊이 n+1까지 있는 형태이다.

이 트리가 갈라지는 형태는 깊이 i에서는 ai가 자식이 둘이고 나머지는 모두 하나인 형태이다.

이때 정점들은 좌에서 우로 번호순으로 배열되어 그림과 같은 형태를 만든다.

 

 

당신은 "정점 x와 y의 LCA(가장 가까운 공통 조상)는 무엇인가?"라는 형태의 q개의 질문을 해결해야 한다.​ 


입력

첫 줄에 n, q, t가 주어진다. (1 ≤ n,q ≤ 200,000, t = 0 or 1)

t는 밑에서 설명할 입력 방식에 사용되는 상수이다.

두 번째 줄에는 a1, ... , an이 차례대로 한 줄에 주어진다.

이후 q줄에 걸쳐 i번째 줄에는 i번째 질의 내용을 구성하는 두 정수 x'i, y'i가 주어진다.

이때 당신이 해결해야할 i번째 질의는 정점 xi와 yi의 LCA를 구하는 것이다.

 

여기서 xi와 yi는 각각

x_i = \left({(\bar{x_i} + t\times z_{i-1}-1) mod {{(n+1)(n+2)}\over 2}}\right) + 1

y_i = \left({(\bar{y_i} + t\times z_{i-1} -1) mod {{(n+1)(n+2)}\over 2}}\right) + 1

 

로 정의되며, zi는 i번째 질의에서의 답을 의미한다.

z0은 편의상 0으로 정의한다.​ 


출력

q줄에 걸쳐 순서대로 주어진 질의에 대한 답을 한줄에 하나씩 출력한다. 


예제 #1

3 5 0

1 2 6

7 10

8 5

6 2

9 10

2 3
1

5

1

6

1

예제 #2

3 5 1

1 2 6

7 10

8 5

6 2

9 10

2 3
1

6

2

1

1

출처

songc
로그인해야 코드를 작성할 수 있어요.