codeforces.com/contest/848/problem/C

import javax.swing.text.Segment;
import java.io.*;
import java.util.*;

public class Main {

    String fileName = "";

    class Query {
        int a, b, c;

        Query(int a, int b, int c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }
    }

    void solve() throws IOException {
        int n = readInt(), m = readInt();
        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = readInt() - 1;
        }
        Set<Integer> prexy[] = new TreeSet[n];  //
        Arrays.fill(prexy, new TreeSet<Integer>());
        int[] lastPosition = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            prexy[i].add(Math.max(lastPosition[arr[i]], i));
            lastPosition[arr[i]] = i;
        }
        Query[] queries = new Query[m];
        TreeSet<Integer>[] sets = new TreeSet[n];
        Arrays.fill(sets, new TreeSet<Integer>());
        for (int i = 0; i < n; i++) {
            sets[arr[i]].add(i);
        }
        for (int i = 0; i < m; i++) {
            queries[i] = new Query(readInt() - 1, readInt() - 1, readInt() - 1);
            if (queries[i].a == 0) {
                int now = queries[i].c;
                if (sets[now].lower(queries[i].b) != null) {
                    int previous_index = sets[now].lower(queries[i].b);
                    if (sets[now].higher(queries[i].b) != null) {
                        sets[now].add(queries[i].c);
                    }
                    sets[previous_index].add(queries[i].c);
                }
            }
        }
        int[][] xy = new int[n][];
        for (int i = 0; i < n; i++) {
            xy[i] = new int[sets[i].size()];
            int currentIndex = 0;
            for (int val : sets[i]) {
                xy[i][currentIndex++] = val;
            }
        }
        for (int i = 0; i < n; i++) {
            sets[i].clear();
        }
        SegmentTree tree = new SegmentTree(xy);
        for (int i = n - 1; i >= 0; i--) {
            sets[arr[i]].add(i);
            tree.update(0, 0, n, i, arr[i], Math.max(i, lastPosition[arr[i]]) - i);
            lastPosition[arr[i]] = i;
        }

        for (int index = 0; index < m; index++) {
            if (queries[index].a == 0) {
                int ind = queries[index].b;
                int newValue = queries[index].c;
                int currentValue = arr[ind];
                if (currentValue == newValue) continue;
                if (sets[currentValue].lower(ind) != null) {
                    int previousIndex = sets[currentValue].lower(ind);
                    tree.update(0, 0, n, previousIndex, ind, 0);
                    if (sets[currentValue].higher(ind) != null) {
                        int nextIndex = sets[currentValue].higher(ind);
                        tree.update(0, 0, n, previousIndex, nextIndex, nextIndex - previousIndex);
                    }
                }

                if(sets[newValue].lower(ind) != null){
                    int previousIndex = sets[newValue].lower(ind);
                    if(sets[newValue].higher(ind) != null){
                        int nextIndex = sets[newValue].higher(ind);
                        tree.update(0, 0, n, previousIndex, nextIndex, 0);
                        tree.update(0, 0, n, ind, nextIndex, nextIndex - ind);
                    } else {
                        tree.update(0 ,0, n, previousIndex, ind, ind - previousIndex);
                    }
                }

                sets[currentValue].remove(ind);
                sets[newValue].add(ind);
                arr[ind] = newValue;
            } else {
                out.print(tree.get(0, 0, n, queries[index].b, queries[index].b, queries[index].c + 1, queries[index].c) + "\n");
            }
        }

    }


    class FenwickTree {
        long[] t;
        int n;

        FenwickTree(int n) {
            this.n = n;
            t = new long[n];
        }

        void add(int i, int val) {
            while (i < n) {
                t[i] += val;
                i = (i + 1) | i;
            }
        }

        long get(int i) {
            long ans = 0;
            while (i >= 0) {
                ans += t[i];
                i = ((i + 1) & i) - 1;
            }
            return ans;
        }

        long get(int l, int r) {
            return get(r) - (l > 0 ? get(l - 1) : 0);
        }
    }

    class Node {
        int[] y;
        FenwickTree tree;

        Node(int[] y) {
            this.y = y;
            tree = new FenwickTree(this.y.length);
        }

        Node(Node l, Node r) {
            TreeSet<Integer> set = new TreeSet<>();
            for (int i : l.y) set.add(i);
            for (int i : r.y) set.add(i);
            this.y = new int[set.size()];
            int currentIndex = 0;
            for (int i : set) {
                this.y[currentIndex++] = i;
            }
            tree = new FenwickTree(this.y.length);
        }

        int getIndex(int value) {
            int left = 0;
            int right = this.y.length - 1;
            int mid;
            int ans = -1;
            while (left <= right) {
                mid = (left + right) / 2;
                if (this.y[mid] <= value) {
                    ans = mid;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            return ans;
        }

        void addValue(int index, int value) {
            tree.add(index, value);
        }

        long get(int l, int r) {
            return tree.get(l, r);
        }
    }

    class SegmentTree {
        Node[] tree;
        int n;

        SegmentTree(int[][] xy) {
            this.n = xy.length;
            tree = new Node[n * 4];
            build(0, 0, n, xy);
        }

        void build(int v, int tl, int tr, int[][] xy) {
            if (tl + 1 == tr) {
                tree[v] = new Node(xy[tl]);
            } else {
                int tm = (tl + tr) / 2;
                build(v * 2 + 1, tl, tm, xy);
                build(v * 2 + 2, tm, tr, xy);
                tree[v] = new Node(tree[v * 2 + 1], tree[v * 2 + 2]);
            }
        }

        void update(int v, int tl, int tr, int x, int y, int val) {
            if (tl + 1 == tr) {
                tree[v].addValue(y, val);
            } else {
                int tm = (tl + tr) / 2;
                if (x < tm) {
                    update(v * 2 + 1, tl, tm, x, y, val);
                } else {
                    update(v * 2 + 2, tm, tr, x, y, val);
                }
                tree[v].addValue(y, val);
            }
        }

        long get(int v, int tl, int tr, int x1, int y1, int x2, int y2) {
            if (tl >= x2 || tr <= x1) return 0;
            if (tl >= x1 && tr <= x2) {
                return tree[v].get(y1, y2);
            } else {
                int tm = (tl + tr) / 2;
                return get(v * 2 + 1, tl, tm, x1, y1, x2, y2) +
                        get(v * 2 + 2, tm, tr, x1, y1, x2, y2);
            }
        }

    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().run();
    }

    void run() throws NumberFormatException, IOException {
        solve();
        out.close();
    }

    BufferedReader in;
    PrintWriter out;

    StringTokenizer tok;
    String delim = " ";

    Main() throws FileNotFoundException {
        try {
            in = new BufferedReader(new FileReader("input.txt"));
            out = new PrintWriter("output.txt");
        } catch (Exception e) {
            if (fileName.isEmpty()) {
                in = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
            } else {
                in = new BufferedReader(new FileReader(fileName + ".in"));
                out = new PrintWriter(fileName + ".out");
            }

        }
        tok = new StringTokenizer("");
    }

    String readLine() throws IOException {
        return in.readLine();
    }

    String readString() throws IOException {
        while (!tok.hasMoreTokens()) {
            String nextLine = readLine();
            if (null == nextLine) {
                return null;
            }

            tok = new StringTokenizer(nextLine);
        }
        return tok.nextToken(delim);
    }

    int readInt() throws NumberFormatException, IOException {
        return Integer.parseInt(readString());
    }

    long readLong() throws NumberFormatException, IOException {
        return Long.parseLong(readString());
    }

    int[] readIntArray(int n) throws NumberFormatException, IOException {
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) {
            a[i] = readInt();
        }
        return a;
    }

    double readDouble() throws NumberFormatException, IOException {
        return Double.parseDouble(readString());
    }

    void sortIntArray(int[] a) {
        Integer[] arr = new Integer[a.length];
        for (int i = 0; i < a.length; i++) {
            arr[i] = a[i];
        }
        Arrays.sort(arr);
        for (int i = 0; i < a.length; i++) {
            a[i] = arr[i];
        }
    }


}