官方题解。来源：清华大学学生算法协会仓库

给定三种记号：

• $s_i\text{#}s_{i+1}$ 表示读完 $s_i$ 后应紧跟 $s_{i+1}$，且优先级高于其它两种符号；
• $s_i\text{*}s_{i+1}$ 表示读完 $s_{i+1}$ 后再读 $s_i$；
• $s_i\text{p-q}$ 表示（在不考虑的情况下）（如果有则）先读对应的 $\text{p-(q-1)}$ 前的文字，读完 $s_i$，再读对应的 $\text{p-(q+1)}$ 前的文字。

给出一个排列 $p_i$，求一组记号使得阅读 $p_i$ 的顺序恰好将其还原为 $1 \sim K$ 的排列。

$1 \le K \le 10^6$

先考虑只有最复杂的 $\text{p-q}$ 时应该怎么处理。

可以想到用栈来保存当前的遥远跳转结构，如果碰到可以直接阅读的则将栈清空。

如果有多个遥远跳转结构怎么办？栈套栈！每弹出一个栈，更新新栈顶的栈的嵌套层数。

在此基础上可以实现另外两种符号，其中 $\text{*}$（及其连续段）需要根据头尾情况简单分类讨论一下。想清楚了实现起来并不复杂。

复杂度 $O(K)$

$z=a+b\mathrm{i}(a,b \in \mathbb{R})$

$Z(a, b)$

$\overrightarrow{OZ}=(a, b)$

$r(\cos\theta+\mathrm{i}\sin\theta)$

$\mathrm{e}^{\mathrm{i}\theta}=\cos\theta+\mathrm{i}\sin\theta$

$z=r\mathrm{e}^{\mathrm{i}\theta}$

$-1=\mathrm{e}^{\mathrm{i}\pi}$

$\mathrm{i}=\mathrm{e}^{\mathrm{i}\frac{\pi}{4}}$

$z_1=r_1\mathrm{e}^{\mathrm{i}\theta_1}, z_2=r_2\mathrm{e}^{\mathrm{i}\theta_2}$

$z_1z_2=r_1\mathrm{e}^{\mathrm{i}\theta_1} \cdot r_2\mathrm{e}^{\mathrm{i}\theta_2}=r_1r_2\mathrm{e}^{\mathrm{i}\theta_1}\mathrm{e}^{\mathrm{i}\theta_2}=r_1r_2\mathrm{e}^{\mathrm{i}(\theta_1+\theta_2)}$

$\frac{z_1}{z_2}=\frac{r_1\mathrm{e}^{\mathrm{i}\theta_1}}{r_2\mathrm{e}^{\mathrm{i}\theta_2}}=\frac{r_1}{r_2}\mathrm{e}^{\mathrm{i}(\theta_1-\theta_2)}$

$\ln\mathrm{i} \quad \sqrt{\mathrm{i}} \quad \mathrm{i}^\mathrm{i} \quad \sin\mathrm{i} \quad \cos\mathrm{i}$