GMOJ S6966 【群岛】

Description

有一条单向的链，满足对于 $1 \leq i < n$，都有一条从点 $i$ 到点 $(i + 1)$ 的有向边。现在还有 $n$ 条边，第 $i$ 条边为从点 $i$ 到点 $a_i$ 的有向边。现在有 $q$ 个独立的询问，分为两类：

1. 将 $a_x$ 改成 $y$。
2. 问你从点 $x$ 出发，能够到达的编号最小的点的编号。

$$1 \leq n, q \leq 10^5$$

Solution