Goodbye Souvenir
Contest: Codeforces Round 431 (Div. 1)
Difficulty rating: 2600
Tags: data structures, divide and conquer

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 format:
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 a1, a2, ..., an (1 ≤ ai ≤ 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 format:
For each query, print one line with an integer — the memory of the recalled subsegment.

Constraints:
Time limit: 6.0 s
Memory limit: 256.0 MB

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.

Example input:
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

Example output:
5
0
7
1

Example input:
7 5
1 3 2 1 4 2 3
1 1 4
2 2 3
1 1 7
2 4 5
1 1 7

Example output:
0
0

Editorial:
Let's look at segment [l, r]. Let's p1x < p2x < ... < pkx — positions of all occurences of shape x at segment [l, r]. Then memory of shape x at segment [l, r] is pkx - p1x = (pkx - pk - 1x) + (pk - 1x - pk - 2x) + ... + (p2x - p1x).
Then we can build array of pairs b: bi = (prev(i), i - prev(i)), where prev(i) — previous occurence of shape ai $$( prev(i) = \max_{1 \leq j < i, \quad a_j = a_i} j )$$. A query transforms to: $$\sum_{l \leq i \leq r, b_i.first \geq l} b_i.second$$, which is variation of counting numbers of greater on segment.
Queries of change in position can be proccessed by recounting values prev(p) for ap and next occurence of that shape before and after changing shape.
Processing of all queries can be done by building segment tree, which every node contains Fenwick tree by types of shape. For reducing memory usage we can, for every node, save only shapes, which appeared in any query for this node. Then Fenwick tree can be build only on this shapes by coordinate compressing.
Result complexity — O(n·log2(n)).