CF848C Goodbye Souvenir

> 在一切被埋葬之前，我不会感到孤独，也不会悲伤... 一串由 $n$ 颗珠子组成的离别信物。珠子从左到右编号为 $1$ 到 $n$，每颗珠子的形状用 $1$ 到 $n$ 之间的整数表示，不同珠子可能有相同形状。 某个珠串子区间中，形状 $x$ 的记忆值定义为该形状最后一次出现位置与首次出现位置的差。整个子区间的记忆值是所有出现形状的记忆值之和。 珠子的形状会随时间改变，记忆值也随之变化。有时需要回忆特定子区间的往事，请你计算每个查询子区间的记忆值。

第一行包含两个整数 $n$ 和 $m$（$1 \leq  n, m \leq 10^5$）——分别表示珠串长度，以及修改和查询的总次数。 第二行包含 $n$ 个整数 $a_1, a_2,\ldots , a_n$（$1 \leq  a_i \leq n$）——表示初始时第 $1, 2, \ldots , n$ 颗珠子的形状。 接下来 $m$ 行每行是以下两种操作之一： - `1 p x` （$1\leq p\leq n$，$1\leq x\leq n$），表示将第 $p$ 颗珠子的形状改为 $x$； - `2 l r` （$1\leq l\leq r\leq n$），表示查询区间 $l$ 到 $r$ 的记忆值。

对于每个查询，输出一行整数——对应子区间的记忆值。

**【样例解释】** 初始珠串形状依次为 $(1, 2, 3, 1, 3, 2, 1)$。 操作与查询按顺序解析如下： 1. `2 3 7`：区间 $[3,7]$ 的记忆值为 $(7-4)+(6-6)+(5-3)=5$； 2. `2 1 3`：区间 $[1,3]$ 的记忆值为 $(1-1)+(2-2)+(3-3)=0$； 3. `1 7 2`：将第 $7$ 颗珠子形状改为 $2$，此时形状序列变为 $(1, 2, 3, 1, 3, 2, 2)$； 4. `1 3 2`：将第 $3$ 颗珠子形状改为 $2$，此时形状序列变为 $(1, 2, 2, 1, 3, 2, 2)$； 5. `2 1 6`：区间 $[1, 6]$ 的记忆值为 $(4 - 1) + (6 - 2) + (5 - 5) = 7$； 6. `2 5 7`：区间 $[5, 7]$ 的记忆值为 $(7 - 6) + (5 - 5) = 1$。