P12894 [蓝桥杯 2025 国 Java B] 智能交通信号灯

蓝桥智慧城市在一条主干道上沿路安装了 $N$ 个智能交通信号灯，这些信号灯按位置从 $1$ 到 $N$ 编号。每个信号灯都有着一种控制模式，对于第 $i$ 个信号灯，其控制模式用 $A_i$ 表示，$A_i$ 是一个大于等于 $1$ 的整数。 为了评估信号灯配置的 “多样性”，交通管理专家提出了一种度量方式：对于任意两个不同位置 $x$ 和 $y$，它们的多样性分数被定义为大于等于 $1$ 的整数中，第一个既不是 $A_x$ 也不是 $A_y$ 的数值，记作 $\text{mex}(A_x, A_y)$。例如，当 $A_x = 1$ 且 $A_y = 2$ 时，$\text{mex}(1, 2) = 3$；当 $A_x = 1$ 且 $A_y = 3$ 时，$\text{mex}(1, 3) = 2$；当 $A_x = 2$ 且 $A_y = 2$ 时，$\text{mex}(2, 2) = 1$。 政府希望通过分析和调整信号灯配置，提升道路通行效率。为此，他们计划执行 $M$ 条操作指令，每条指令为以下两类之一： - $1\ l\ r$：查询操作。计算所有满足 $l \leq i < j \leq r$ 的信号灯对 $(A_i, A_j)$，其多样性分数 $\text{mex}(A_i, A_j)$ 的总和。 - $2\ k\ x$：调整操作。将第 $k$ 个信号灯的控制模式 $A_k$ 修改为新的值 $x$。 现在，请你协助政府依次处理这 $M$ 次操作，并输出每个查询操作的结果。

第一行包含两个整数 $N$ 和 $M$，分别表示信号灯的数量和操作指令的数量。 第二行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N$，表示初始的信号灯控制模式。 接下来 $M$ 行，每行描述一条操作指令，格式如上所述。

对于每个查询操作，输出一行包含一个整数，表示多样性分数的总和。

**【样例说明】** 初始时信号灯的控制模式依次为：$1, 2, 3, 4, 5$。第一次查询区间 $[1, 5]$，$\text{mex}$ 值分别为 $3, 2, 2, 2, 1, 1, 1, 1, 1, 1$，总和为 $15$。 第二次操作后，信号灯的控制模式依次为：$2, 2, 3, 4, 5$。第二次查询区间 $[1, 5]$，$\text{mex}$ 值均为 $1$，总和为 $10$。 **【评测用例规模与约定】** 对于 $10\%$ 的评测用例，$2 \leq N, M \leq 100$，$1 \leq l < r \leq N$，$1 \leq k \leq N$，$1 \leq A_i, x \leq 10^3$。 对于 $40\%$ 的评测用例，$2 \leq N, M \leq 10^3$，$1 \leq l < r \leq N$，$1 \leq k \leq N$，$1 \leq A_i, x \leq 10^5$。 对于 $100\%$ 的评测用例，$2 \leq N, M \leq 10^5$，$1 \leq l < r \leq N$，$1 \leq k \leq N$，$1 \leq A_i, x \leq 10^9$。