#include <bits/stdc++.h>
using namespace std;


// print tuples {{{

template <size_t index, size_t len, typename ...Ts>
struct print_tuple {
    void operator()(ostream& os, const tuple<Ts...>& t) {
        os << '(' << get<index>(t) << ')';
        print_tuple<index + 1, len, Ts...>()(os, t);
    }
};

template <size_t len, typename ...Ts>
struct print_tuple<len, len, Ts...> {
    void operator()(ostream&, const tuple<Ts...>&) {
    }
};

template <typename ...Ts>
ostream& operator<<(ostream& os, const tuple<Ts...>& t) {
    os << '[';
    print_tuple<0, tuple_size<tuple<Ts...>>::value, Ts...>()(os, t);
    os << ']';
    return os;
}

template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& t) {
    return os << make_tuple(t.first, t.second);
}

// todo: structs with headers

// }}}
// print containers {{{
constexpr size_t print_limit = 10;
template <typename It>
void print(ostream& os, It begin, It end, size_t len) {
    size_t count = 0;
    os << "{";
    while (begin != end && count < print_limit) {
        os << "(" << *begin << ")";
        count++;
        begin++;
    }
    if (begin != end)
        os << "... " << len << " total";
    os << "}";
}
#define MAKE_PRINTER_1(container) \
template <typename T> \
ostream& operator<<(ostream& os, const container<T>& t) { \
    print(os, t.begin(), t.end(), t.size()); \
    return os; \
}
#define MAKE_PRINTER_2(container) \
template <typename T1, typename T2> \
ostream& operator<<(ostream& os, const container<T1, T2>& t) { \
    print(os, t.begin(), t.end(), t.size()); \
    return os; \
}
MAKE_PRINTER_1(vector)
MAKE_PRINTER_2(map)
MAKE_PRINTER_1(set)
MAKE_PRINTER_2(unordered_map)
MAKE_PRINTER_1(unordered_set)
#undef MAKE_PRINTER_1
#undef MAKE_PRINTER_2
// }}}
// geo {{{
constexpr size_t MAXX = 10000;

struct P {
    int64_t x;
    int64_t y;
};

namespace std {
template<>
struct hash<P> {
    size_t operator()(const P& p) const {
        auto h = hash<int64_t>();
        return 13 + ((69 + h(p.x)) ^ h(p.y));
    }
};
}

struct L {
    P a;
    P b;
};

namespace std {
template<>
struct hash<L> {
    size_t operator()(const L& l) const {
        auto h = hash<P>();
        return 42 + ((666 + h(l.a)) ^ h(l.b)); 
    }
};
}

bool operator==(P p1, P p2) { return p1.x == p2.x && p1.y == p2.y; }

bool operator==(L l1, L l2) { return l1.a == l2.a && l1.b == l2.b; }

bool parallel_line(P p1, P p2, P p3, P p4) {
    auto x1 = p2.x - p1.x, x2 = p4.x - p3.x, y1 = p2.y - p1.y, y2 = p4.y - p3.y;
    return x1 * y2 == x2 * y1; 
}

bool same_line(P p1, P p2, P p3) {
    return parallel_line(p1, p2, p1, p3);
}
// }}}
// turbomap {{{
namespace std {
template<>
struct hash<pair<uint16_t, uint16_t>> {
    size_t operator()(const pair<uint16_t, uint16_t>& p) const {
        auto h = hash<size_t>();
        return 13 + ((69 + h(p.first)) ^ h(p.second));
    }
};
}

using A = uint32_t;
class turbomap {
public:
    void increment(A e1, A e2, int32_t v) {
        s[first_idx(e1, e2)][second_idx(e1, e2)] += v;
    }
    int32_t get(A e1, A e2) {
        const auto it = s[first_idx(e1, e2)].find(second_idx(e1, e2));
        if (it == s[first_idx(e1, e2)].end())
            return 0;
        return it->second;
    }
private:
    unordered_map<pair<uint16_t, uint16_t>, int32_t> s[256];
    uint8_t first_idx(A e1, A e2) {
        return smaller_part(min(e1, e2)) + 16u * smaller_part(max(e1, e2));
    }
    pair<uint16_t, uint16_t> second_idx(A e1, A e2) {
        return make_pair(bigger_part(min(e1, e2)), bigger_part(max(e1, e2)));
    }
    uint16_t bigger_part(A e) {
        return static_cast<uint16_t>(e & ((1u << 16u) - 1u));
    }
    uint8_t smaller_part(A e) {
        return static_cast<uint8_t>((e << 16u) & 16u);
    }
    friend ostream& operator<<(ostream& os, const turbomap& m) {
        return os << "multimap" << m.s[0];
    }
};
// }}}
// bit operations {{{
template <typename T>
T nextPow2(T x, bool strictly_greater = false) {
    T y = 1;
    while (y < x)
        y <<= 1;
    if (y == x && strictly_greater)
        y <<= 1;
    return y;
}
// }}}

using A = uint32_t;
A n;
vector<A> as;
vector<A> aprev, anext;

vector<int32_t> p;
turbomap m;

vector<set<A>> aps;

struct PT {
    A p;
    bool l_whole, r_whole;
};
PT pt_parent(A a1, A a2) {
    PT pt;
    while (a1 != a2) {
        if (a1 % 2 == 1)
            pt.l_whole = false;
        if (a2 % 2 == 0)
            pt.r_whole = false;
        a1 /= 2;
        a2 /= 2;
    }
    pt.p = a1;
    return pt;
}

vector<A> pt_intervals(A l, A r) {
//    cerr << "pt_intervals " << l << "," << r << endl;
    const auto pt = pt_parent(l, r);
    if (pt.l_whole && pt.r_whole)
        return {pt.p};
    vector<A> v;
    if (pt.l_whole)
        v.push_back(pt.p * 2);
    else {
        while (l / 2 != pt.p) {
            if (l % 2 == 1)
                v.push_back(l++);
            l /= 2;
        }
    }
    if (pt.r_whole)
        v.push_back(pt.p * 2 + 1);
    else {
        while (r / 2 != pt.p) {
            if (r % 2 == 0)
                v.push_back(r--);
            r /= 2;
        }
    }
    return v;
}
void test_intervals() {
    while (true) {
        size_t a, b;
        cin >> a >> b;
        auto v = pt_intervals(a, b);
        cout << v << endl;
    }
}

void handle(size_t a, size_t b, int32_t v) {
    a += p.size() / 2;
    b += p.size() / 2;
    vector<A> av, bv;
    while (a != b) {
        if (a % 2 == 1)
            av.push_back(a);
        if (b % 2 == 0)
            bv.push_back(b);
        a /= 2;
        b /= 2;
    }
    av.push_back(a * 2);
    bv.push_back(b * 2 + 1);
    for (const auto ax : av)
        for (const auto bx : bv)
            m.increment(ax, bx, v);
    while (a) {
        p[a] += v;
        a /= 2;
    }
}

void regen_anext_aprev(A idx, A new_a) {
    auto old_a = as[idx];
    aps[old_a].erase(aps[old_a].find(idx));
    auto prev_idx = n;
    auto next_idx = n;
    if (!aps[new_a].empty()) {
        auto it_next = aps[new_a].upper_bound(idx);
        if (it_next != aps[new_a].end()) {
            next_idx = *it_next;
            if (it_next != aps[new_a].begin())
                prev_idx = *(--it_next);
        } else
            prev_idx = *aps[new_a].rbegin();
    }
    if (aprev[idx] != n)
        anext[aprev[idx]] = anext[idx];
    if (anext[idx] != n)
        aprev[anext[idx]] = aprev[idx];
    aprev[idx] = prev_idx;
    anext[idx] = next_idx;
    if (aprev[idx] != n)
        anext[aprev[idx]] = idx;
    if (anext[idx] != n)
        aprev[anext[idx]] = idx;
    aps[new_a].insert(idx);
    as[idx] = new_a;
}

void go() {
    size_t q;
    cin >> n >> q;
    vector<size_t> last_pos(n, n);
    aprev = vector<A>(n, n);
    anext = vector<A>(n, n);
    aps.resize(n);
    as.resize(n);
    for (size_t i = 0; i < n; i++) {
        size_t a;
        cin >> a;
        a--;
        as[i] = a;
        aps[a].insert(i);
        if (last_pos[a] != n) {
            aprev[i] = last_pos[a];
            anext[last_pos[a]] = i;
        }
        last_pos[a] = i;
    }
    p.resize(nextPow2(n, false) * 2);
    for (size_t i = 0; i < n; i++) {
        if (anext[i] != n) {
            const size_t memory = anext[i] - i;
            handle(i, anext[i], memory);
        }
    }
//    cerr << p << endl;
//    cerr << m << endl;
    //cerr << "as " << as << endl;
    //cerr << "aprev " << aprev << endl;
    //cerr << "anext " << anext << endl;
    for (size_t i = 0; i < q; i++) {
        uint16_t tp;
        cin >> tp;
        if (tp == 2) {
            A l_input, r_input;
            cin >> l_input >> r_input;
            l_input--;
            r_input--;
            int32_t ans = 0;
            vector<A> pv = pt_intervals(l_input + p.size() / 2, r_input + p.size() / 2);
//            cerr << pv << endl;
            for (size_t pv1 = 0; pv1 < pv.size(); pv1++)
                for (size_t pv2 = pv1 + 1; pv2 != pv.size(); pv2++)
                    ans += m.get(pv[pv1], pv[pv2]);
            for (const auto pv0 : pv)
                ans += p[pv0];
            cout << ans << endl;
        } else {
            A idx, x;
            cin >> idx >> x;
//            cerr << "tp " << tp << " not implemented" << endl;
            idx--;
            x--;
            if (aprev[idx] != n)
                handle(aprev[idx], idx, -(idx - aprev[idx]));
            if (anext[idx] != n)
                handle(idx, anext[idx], -(anext[idx] - idx));
            if (anext[idx] != n && aprev[idx] != n)
                handle(aprev[idx], anext[idx], anext[idx] - aprev[idx]);
            regen_anext_aprev(idx, x);
            if (aprev[idx] != n)
                handle(aprev[idx], idx, (idx - aprev[idx]));
            if (anext[idx] != n)
                handle(idx, anext[idx], (anext[idx] - idx));
            if (anext[idx] != n && aprev[idx] != n)
                handle(aprev[idx], anext[idx], -(anext[idx] - aprev[idx]));
            //cerr << "set " << idx << " to " << x << endl;
            //cerr << "aprev " << aprev << endl;
            //cerr << "anext " << anext << endl;
         }
    }
}

int main () { // {{{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    test_intervals();
    go();
} // }}}
