P15599 [ICPC 2020 Jakarta R] Token Distance

你正在玩一个棋盘游戏，棋盘上有编号从 $0$ 到 $10^9$（包含端点）的方格，以及 $N$ 个编号从 $1$ 到 $N$ 的令牌。每个令牌位于某个方格中，多个令牌可以位于同一方格。初始时，令牌 $i$ 位于方格 $T_i$ 中。两个令牌的距离是指第一个令牌所在方格编号与第二个令牌所在方格编号的差。 对于一组令牌 $S$，我们按以下方式检查它们是否 **分隔良好**： - 令 $A$ 为 $S$ 中的令牌按所在方格编号升序排列的列表。若多个令牌位于同一方格，则这些令牌按令牌编号升序排列。 - 如果 $A$ 中令牌少于三个，则该组令牌是分隔良好的。 - 否则，该组令牌是分隔良好的当且仅当 $A$ 中相邻令牌之间的距离相等。两个令牌在 $A$ 中相邻是指它们的下标相差 $1$。 你需要执行 $Q$ 次操作，操作类型如下： 1. 将令牌 $X$ 移动到方格 $Y$。 2. 报告编号从 $L$ 到 $R$（包含端点）的令牌集合是否分隔良好。

输入第一行包含两个整数 $N$ 和 $Q$（$2 \leq N \leq 100\,000$；$1 \leq Q \leq 100\,000$），分别表示令牌的数量和操作的数量。下一行包含 $N$ 个整数 $T_i$（$0 \leq T_i \leq 10^9$），表示令牌的初始方格位置。接下来 $Q$ 行，每行包含以下格式之一，表示你要执行的操作： - $1\ X\ Y$（$1 \leq X \leq N$；$0 \leq Y \leq 10^9$） 将令牌 $X$ 移动到方格 $Y$。 - $2\ L\ R$（$1 \leq L < R \leq N$） 输出编号从 $L$ 到 $R$（包含端点）的令牌集合是否分隔良好。 保证至少有一个第二类操作。

对于每个第二类操作，按输入顺序输出一行字符串 **"YES"** 或 **"NO"**，表示该令牌集合是否分隔良好。

#### 样例 #1 解释 - 初始时，令牌位于方格 $[1, 1, 1, 10, 1]$。 - 对于第一个操作，$A = [1, 2, 3]$ 中相邻令牌的距离为 $0$ 和 $0$，因此令牌分隔良好。 - 对于第二个操作，$A = [1, 2, 3, 5, 4]$ 中相邻令牌的距离为 $0, 0, 0$ 和 $9$，因此令牌分隔不好。 - 经过第三和第四个操作后，令牌位于方格 $[1, 1, 7, 10, 4]$。 - 对于第五个操作，$A = [2, 3, 4]$ 中相邻令牌的距离为 $6$ 和 $3$，因此令牌分隔不好。 - 对于第六个操作，$A = [2, 5, 3, 4]$ 中相邻令牌的距离为 $3, 3$ 和 $3$，因此令牌分隔良好。 - 对于第七个操作，$A = [5, 4]$ 中令牌少于三个，根据定义，令牌分隔良好。 翻译由 DeepSeek 完成