Goodbye Souvenir

题意翻译

给定长度为$n$的数组, 定义数字$X$在$[l,r]$内的值为数字$X$在$[l,r]$内最后一次出现位置的下标减去第一次出现位置的下标 给定$m$次询问, 每次询问有三个整数$a, b, c$,询问规则如下: 当$a = 1$时, 将数组内第$b$个元素更改为$c$ 当$a = 2$时, 求区间$[b,c]$所有数字的值的和 输入: 第一行两个整数$n,m$ 第二行$n$个整数, 表示数组 第$3-3 + m$行, 每行三个整数, 表示每次询问 输出: 对于每次$a = 2$的询问, 输出一个整数表示答案

题目描述

I won't feel lonely, nor will I be sorrowful... not before everything is buried. A string of $ n $ beads is left as the message of leaving. The beads are numbered from $ 1 $ to $ n $ from left to right, each having a shape numbered by integers between $ 1 $ and $ n $ inclusive. Some beads may have the same shapes. The memory of a shape $ x $ in a certain subsegment of beads, is defined to be the difference between the last position and the first position that shape $ x $ appears in the segment. The memory of a subsegment is the sum of memories over all shapes that occur in it. From time to time, shapes of beads change as well as the memories. Sometimes, the past secreted in subsegments are being recalled, and you are to find the memory for each of them.

输入输出格式

输入格式

The first line of input contains two space-separated integers $ n $ and $ m $ ( $ 1<=n,m<=100000 $ ) — the number of beads in the string, and the total number of changes and queries, respectively. The second line contains $ n $ integers $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=n $ ) — the initial shapes of beads $ 1,2,...,n $ , respectively. The following $ m $ lines each describes either a change in the beads or a query of subsegment. A line has one of the following formats: - 1 p x ( $ 1<=p<=n $ , $ 1<=x<=n $ ), meaning that the shape of the $ p $ -th bead is changed into $ x $ ; - 2 l r ( $ 1<=l<=r<=n $ ), denoting a query of memory of the subsegment from $ l $ to $ r $ , inclusive.

输出格式

For each query, print one line with an integer — the memory of the recalled subsegment.

输入输出样例

输入样例 #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

说明

The initial string of beads has shapes $ (1,2,3,1,3,2,1) $ . Consider the changes and queries in their order: 1. 2 3 7: the memory of the subsegment $ [3,7] $ is $ (7-4)+(6-6)+(5-3)=5 $ ; 2. 2 1 3: the memory of the subsegment $ [1,3] $ is $ (1-1)+(2-2)+(3-3)=0 $ ; 3. 1 7 2: the shape of the $ 7 $ -th bead changes into $ 2 $ . Beads now have shapes $ (1,2,3,1,3,2,2) $ respectively; 4. 1 3 2: the shape of the $ 3 $ -rd bead changes into $ 2 $ . Beads now have shapes $ (1,2,2,1,3,2,2) $ respectively; 5. 2 1 6: the memory of the subsegment $ [1,6] $ is $ (4-1)+(6-2)+(5-5)=7 $ ; 6. 2 5 7: the memory of the subsegment $ [5,7] $ is $ (7-6)+(5-5)=1 $ .

题意翻译

给定长度为$n$的数组, 定义数字$X$在$[l,r]$内的值为数字$X$在$[l,r]$内最后一次出现位置的下标减去第一次出现位置的下标 给定$m$次询问, 每次询问有三个整数$a, b, c$,询问规则如下: 当$a = 1$时, 将数组内第$b$个元素更改为$c$ 当$a = 2$时, 求区间$[b,c]$所有数字的值的和 输入: 第一行两个整数$n,m$ 第二行$n$个整数, 表示数组 第$3-3 + m$行, 每行三个整数, 表示每次询问 输出: 对于每次$a = 2$的询问, 输出一个整数表示答案