스턴–브로코 트리

다음 내용은 모든 문제에 적용된다.

• 입력과 출력의 양의 유리수는 기약분수 $a/b$로 표현된다.
• 양의 유리수는 Stern–Brocot Tree의 노드와 동일시된다(SBT).
• SBT의 노드 $a/b$가 입력에 나타나는 경우, $a, b$는 다음 제약 조건을 만족한다: $1\leq a \leq 1000000000$ , $1\leq b \leq 1000000000$ , $a$ 및 $b$는 서로소이다.

다음 목록에는 SBT와 관련된 $T$개의 문제가 주어진다.

ENCODE_PATH

SBT에서 $1/1$부터 $a/b$까지의 경로를 왼쪽으로 이동할 때는 L, 오른쪽으로 이동할 때는 R을 사용하여 문자열로 나타낸다. 이 문자열을 실행 길이 부호화로 압축하고 다음 형식으로 출력한다.

$k$ $c_0$ $n_0$ $c_1$ $n_1$ $\ldots$ $c_{k-1}$ $n_{k-1}$

여기서 $c_i$는 L 또는 R이고, $n_i$는 연속한 $c_i$의 개수를 나타내는 양의 정수이다.

@{keyword.input}

ENCODE_PATH $a$ $b$

@{keyword.output}

$k$ $c_0$ $n_0$ $c_1$ $n_1$ $\ldots$ $c_{k-1}$ $n_{k-1}$

DECODE_PATH

$1/1$부터 $a/b$까지의 경로가 ENCODE_PATH의 형식으로 주어진다. $a, b$를 출력한다.

@{keyword.constraints}

• $c_i\neq c_{i+1}$
• $1\leq n_i\leq 10^9$
• 정답이 $1\leq a\leq 10^9$와 $1\leq b\leq 10^9$을 만족함이 보장된다.

@{keyword.input}

DECODE_PATH $k$ $c_0$ $n_0$ $c_1$ $n_1$ $\ldots$ $c_{k-1}$ $n_{k-1}$

@{keyword.output}

$a$ $b$

LCA

$a/b$와 $c/d$의 LCA $f/g$를 출력한다.

@{keyword.input}

LCA $a$ $b$ $c$ $d$

@{keyword.output}

$f$ $g$

ANCESTOR

깊이가 $k$인 $a/b$의 조상 $f/g$을 출력한다. 존재하지 않으면 -1만 출력한다.

@{keyword.constraints}

• $1 \leq k\leq 1000000000$

@{keyword.input}

ANCESTOR $k$ $a$ $b$

@{keyword.output}

$f$ $g$

RANGE

a/b의 자손들의 집합은 유리수의 열린 구간을 이룬다. 이 구간의 하한 $f/g$와 상한 $h/k$을 출력한다. 예외적으로 $0$에는 0 1을, $+\infty$에는 1 0을 출력한다.

@{keyword.input}

RANGE $a$ $b$

@{keyword.output}

$f$ $g$ $h$ $k$

제약 조건

• $1 \leq T \leq 100000$

$T$
$\text{query}_0$
$\text{query}_1$
$\vdots$
$\text{query}_{T-1}$

각 문제의 정답을 별도의 줄에 출력한다.