P15759 [JAG 2025 Summer Camp #1] Walking on Binary Tree

给定一棵无限完全二叉树，其顶点用正整数标记。根节点为顶点 $1$，对于每个顶点 $x$（$x \geq 2$），其父节点是 $\left\lfloor \frac{x}{2} \right\rfloor$。 同时给定一个长度为 $N$ 的字符串 $S = S_0 S_1 \ldots S_{N-1}$。$S$ 的每个字符是 `L` 或 `R`。 考虑以下过程：你当前位于某个顶点 $u$，希望通过在树中反复移动到达顶点 $v$。 在第 $i$ 次移动（从 1 开始计数）时，假设你位于顶点 $x$。你可以选择以下移动之一： **向下移动：** 如果 $S_{(i-1) \bmod N}$ 是 `L`，则移动到顶点 $2x$。否则，移动到顶点 $2x + 1$。 **向上移动：** 仅当 $x \geq 2$ 时可以选择。移动到顶点 $\left\lfloor \frac{x}{2} \right\rfloor$。 注意，你不能停留在同一个顶点。 给定 $Q$ 个独立的询问。在第 $i$ 个询问中，你从顶点 $u_i$ 出发，想要到达顶点 $v_i$。 对于每个询问，判断是否可能从 $u_i$ 到达 $v_i$。如果可能，求出所需的最少移动次数。

输入格式如下： $$\begin{aligned} & N \\ & S \\ & Q \\ & u_1 \ v_1 \\ & u_2 \ v_2 \\ & \vdots \\ & u_Q \ v_Q \end{aligned}$$ - $1 \leq N \leq 10^6$ - $1 \leq Q \leq 200\,000$ - $1 \leq u_i, v_i \leq 10^{18}$ ($1 \leq i \leq Q$) - $N$、$Q$、$u_i$ 和 $v_i$ 是整数。 - $S$ 是一个长度为 $N$ 的字符串，由 `L` 和 `R` 组成。

输出 $Q$ 行。在第 $i$ 行，如果可以从 $u_i$ 到达 $v_i$，则输出所需的最少移动次数；否则输出 `-1`。

翻译由 DeepSeek V3.2 完成