Stern-Brocot 树

【题目描述】

以下事实对所有子问题都成立。

• 输入/输出中的正有理数用最简分数 $a/b$ 表示。
• 正有理数与 Stern–Brocot 树（SBT）中的节点视为等同。
• 如果 SBT 的节点 $a/b$ 出现在输入中，那么 $a, b$ 满足以下限制：$1\leq a \leq 1000000000$，$1\leq b \leq 1000000000$，且 $a$ 与 $b$ 互质。

给出 $T$ 个与 SBT 相关的问题，类型如下。

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$ 的个数。

输入格式：

ENCODE_PATH $a$ $b$

输出格式：

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

DECODE_PATH

以 ENCODE_PATH 的格式给出从 $1/1$ 到 $a/b$ 的路径。输出 $a, b$。

数据范围：

• $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$。

输入格式：

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

输出格式：

$a$ $b$

LCA

输出 $a/b$ 与 $c/d$ 的最近公共祖先（LCA）$f/g$。

输入格式：

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

输出格式：

$f$ $g$

ANCESTOR

输出 $a/b$ 的深度为 $k$ 的祖先 $f/g$。若不存在，输出 -1。

数据范围：

• $1 \leq k\leq 1000000000$

输入格式：

ANCESTOR $k$ $a$ $b$

输出格式：

$f$ $g$

RANGE

SBT 中 $a/b$ 的所有后代构成有理数集合，它是一个开区间。输出该区间的下确界 $f/g$ 与上确界 $h/k$。特殊地，下确界为 $0$ 时输出 0 1，上确界为 $+\infty$ 时输出 1 0。

输入格式：

RANGE $a$ $b$

输出格式：

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

【输入】

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

【输出】

对每个问题输出一行答案。

【输入样例】

10
DECODE_PATH 0
DECODE_PATH 3 R 2 L 1 R 2
ENCODE_PATH 1 1
ENCODE_PATH 5 11
LCA 2 3 3 5
LCA 5439 19294 8291 29410
ANCESTOR 10 1 1
ANCESTOR 300 1000000000 1
RANGE 1 1
RANGE 11 8

【输出样例】

1 1
11 4
0
2 L 2 R 4
2 3
148 525
-1
301 1
0 1 1 0
4 3 7 5

【数据范围】

• $1 \leq T \leq 100000$

【来源】

Library Checker（yosupo06） stern_brocot_tree