English · Original
Chinese · Translation
Formal · Original
_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.
## Input
The first line of input contains two space-separated integers _n_ and _m_ (1 ≤ _n_, _m_ ≤ 100 000) — 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.
## Output
For each query, print one line with an integer — the memory of the recalled subsegment.
[samples]
## Note
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.
_I won't feel lonely, nor will I be sorrowful... not before everything is buried._
一条由 #cf_span[n] 颗珠子组成的字符串被留下作为告别的讯息。珠子从左到右编号为 #cf_span[1] 到 #cf_span[n]，每颗珠子具有一个形状，形状编号为介于 #cf_span[1] 和 #cf_span[n] 之间的整数（含端点）。某些珠子可能具有相同的形状。
在某个珠子子段中，形状 #cf_span[x] 的 #cf_span(class=[tex-font-style-underline], body=[memory]) 定义为该形状在该子段中最后一次出现的位置与第一次出现的位置之差。一个子段的 #cf_span(class=[tex-font-style-underline], body=[memory]) 是其包含的所有形状的 #cf_span(class=[tex-font-style-underline], body=[memories]) 之和。
随着时间推移，珠子的形状会改变，#cf_span(class=[tex-font-style-underline], body=[memories]) 也随之变化。有时，子段中隐藏的过往会被回忆起来，你需要为每个这样的子段找出其 #cf_span(class=[tex-font-style-underline], body=[memory])。
输入的第一行包含两个用空格分隔的整数 #cf_span[n] 和 #cf_span[m] (#cf_span[1 ≤ n, m ≤ 100 000]) —— 分别表示字符串中珠子的数量，以及更改和查询的总次数。
第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ n]) —— 分别表示珠子 #cf_span[1, 2, ..., n] 的初始形状。
接下来的 #cf_span[m] 行每行描述一次对珠子的更改或一次对子段的查询。每行具有以下格式之一：
对于每个查询，请输出一行一个整数 —— 所回忆子段的 #cf_span(class=[tex-font-style-underline], body=[memory])。
初始的珠子序列形状为 #cf_span[(1, 2, 3, 1, 3, 2, 1)]。
按顺序考虑以下更改和查询：
## Input
输入的第一行包含两个用空格分隔的整数 #cf_span[n] 和 #cf_span[m] (#cf_span[1 ≤ n, m ≤ 100 000]) —— 分别表示字符串中珠子的数量，以及更改和查询的总次数。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ n]) —— 分别表示珠子 #cf_span[1, 2, ..., n] 的初始形状。接下来的 #cf_span[m] 行每行描述一次对珠子的更改或一次对子段的查询。每行具有以下格式之一：
_1 p x_ (#cf_span[1 ≤ p ≤ n], #cf_span[1 ≤ x ≤ n])，表示将第 #cf_span[p] 颗珠子的形状改为 #cf_span[x]；
_2 l r_ (#cf_span[1 ≤ l ≤ r ≤ n])，表示查询子段 #cf_span[l] 到 #cf_span[r]（含端点）的 #cf_span(class=[tex-font-style-underline], body=[memory])。
## Output
对于每个查询，请输出一行一个整数 —— 所回忆子段的 #cf_span(class=[tex-font-style-underline], body=[memory])。
[samples]
## Note
初始的珠子序列形状为 #cf_span[(1, 2, 3, 1, 3, 2, 1)]。按顺序考虑以下更改和查询：
_2 3 7_：子段 #cf_span[[3, 7]] 的 #cf_span(class=[tex-font-style-underline], body=[memory]) 为 #cf_span[(7 - 4) + (6 - 6) + (5 - 3) = 5]；
_2 1 3_：子段 #cf_span[[1, 3]] 的 #cf_span(class=[tex-font-style-underline], body=[memory]) 为 #cf_span[(1 - 1) + (2 - 2) + (3 - 3) = 0]；
_1 7 2_：第 #cf_span[7] 颗珠子的形状变为 #cf_span[2]。此时珠子形状为 #cf_span[(1, 2, 3, 1, 3, 2, 2)]；
_1 3 2_：第 #cf_span[3] 颗珠子的形状变为 #cf_span[2]。此时珠子形状为 #cf_span[(1, 2, 2, 1, 3, 2, 2)]；
_2 1 6_：子段 #cf_span[[1, 6]] 的 #cf_span(class=[tex-font-style-underline], body=[memory]) 为 #cf_span[(4 - 1) + (6 - 2) + (5 - 5) = 7]；
_2 5 7_：子段 #cf_span[[5, 7]] 的 #cf_span(class=[tex-font-style-underline], body=[memory]) 为 #cf_span[(7 - 6) + (5 - 5) = 1]。
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $ denote the number of beads and the number of operations, respectively.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of integers, where $ a_i \in \{1, 2, \dots, n\} $ represents the shape of the $ i $-th bead.
For a subsegment $ [l, r] $ (with $ 1 \leq l \leq r \leq n $) and a shape $ x $, define:
- $ \text{first}(x, [l,r]) = \min\{ i \in [l, r] \mid a_i = x \} $, if $ x $ appears in $ [l, r] $;
- $ \text{last}(x, [l,r]) = \max\{ i \in [l, r] \mid a_i = x \} $, if $ x $ appears in $ [l, r] $.
The **memory** of shape $ x $ in $ [l, r] $ is:
$$
\text{memory}(x, [l,r]) =
\begin{cases}
\text{last}(x, [l,r]) - \text{first}(x, [l,r]) & \text{if } x \text{ appears in } [l, r], \\
0 & \text{otherwise}.
\end{cases}
$$
The **memory** of subsegment $ [l, r] $ is:
$$
\text{memory}([l,r]) = \sum_{x=1}^{n} \text{memory}(x, [l,r])
$$
**Constraints**
1. $ 1 \leq n, m \leq 100{,}000 $
2. $ 1 \leq a_i \leq n $ for all $ i \in \{1, \dots, n\} $
3. Each operation is one of:
- Update: `1 p x` — set $ a_p \leftarrow x $, where $ 1 \leq p \leq n $, $ 1 \leq x \leq n $
- Query: `2 l r` — compute $ \text{memory}([l,r]) $, where $ 1 \leq l \leq r \leq n $
**Objective**
For each query operation `2 l r`, output $ \text{memory}([l,r]) $.
API Response (JSON)
{
"problem": {
"name": "E. Goodbye Souvenir",
"description": {
"content": "_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, ea",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 6000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF849E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "_I won't feel lonely, nor will I be sorrowful... not before everything is buried._\n\nA string of _n_ beads is left as the message of leaving. The beads are numbered from 1 to _n_ from left to right, ea...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "_I won't feel lonely, nor will I be sorrowful... not before everything is buried._\n\n一条由 #cf_span[n] 颗珠子组成的字符串被留下作为告别的讯息。珠子从左到右编号为 #cf_span[1] 到 #cf_span[n]，每颗珠子具有一个形状，形状编号为介于 #cf_span[1] 和 #cf_span[n]...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the number of beads and the number of operations, respectively. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers, where $ a_i \\in \\...",
"is_translate": false,
"language": "Formal"
}
]
}