← 返回题目列表

Codeforces · 848/C

C. 再见纪念品

中文机器翻译题面 查看原题

我不会感到孤独,也不会悲伤……在一切都被埋葬之前。

留下一串n颗珠子作为离开的信息。珠子从左到右编号为1到n,每个珠子具有由1到n之间的整数编号的形状。有些珠子可能具有相同的形状。

珠子的某个子段中形状 x 的记忆被定义为形状 x 在该段中出现的最后位置和第一个位置之间的差异。子段的记忆是其中出现的所有形状的记忆的总和。

珠子的形状和记忆有时会发生变化。有时,隐藏在子片段中的过去正在被回忆起来,你要找到每个片段的记忆。

输入

输入的第一行包含两个空格分隔的整数 n 和 m (1 ≤ n, m ≤ 100 000) — 分别是字符串中珠子的数量以及更改和查询的总数。

第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ n) - 分别是珠子 1, 2, ..., n 的初始形状。

接下来的 m 行每行描述珠子的变化或子段的查询。一行具有以下格式之一:

- 1 p x (1 ≤ p ≤ n, 1 ≤ x ≤ n),表示第p个珠子的形状变为x;
- 2 l r (1 ≤ l ≤ r ≤ n),表示查询从l到r(含)的子段的内存。

输出

对于每个查询,打印一行并包含一个整数——调用的子段的内存。

示例

输入 #1

7 6
1 2 3 1 3 2 1
2 3 7
2 1 3
1 7 2
1 3 2
2 1 6
2 5 7

输出 #1

5
0
7
1

输入 #2

7 5
1 3 2 1 4 2 3
1 1 4
2 2 3
1 1 7
2 4 5
1 1 7

输出 #2

0
0

注意

初始珠串的形状为 (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。