Untitled

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

const int N = 3e5 + 9;
#define int long long
struct node
{
    int cnt[41] = {0};
    int inv;
};

int a[N], n, q;
node marge(node l, node r)
{
    node res;
    res.inv = l.inv + r.inv;
    for (int i = 1; i <= 40; i++)
    {
        if (l.cnt[i] == 0)
            continue;
        for (int j = 1; j < i; j++)
        {
            res.inv += l.cnt[i] * r.cnt[j];
        }
    }
    for (int i = 1; i <= 40; i++)
    {
        res.cnt[i] = l.cnt[i] + r.cnt[i];
    }
    return res;
}
struct ST
{
    node t[4 * N];
    static const int inf = 1e9;
    void build(int n, int b, int e)
    {
        if (b == e)
        {
            t[n].cnt[a[b]] = 1;
            t[n].inv = 0;
            return;
        }
        int mid = (b + e) >> 1, l = n << 1, r = l | 1;
        build(l, b, mid);
        build(r, mid + 1, e);
        t[n] = marge(t[l], t[r]);
    }
    void upd(int n, int b, int e, int i, int x)
    {
        if (b > i || e < i)
            return;
        if (b == e && b == i)
        {
            t[n].cnt[a[i]]--;
            t[n].cnt[x]++;
            return;
        }
        int mid = (b + e) >> 1, l = n << 1, r = l | 1;
        upd(l, b, mid, i, x);
        upd(r, mid + 1, e, i, x);
        t[n] = marge(t[l], t[r]);
    }
    node query(int n, int b, int e, int i, int j)
    {
        if (b > j || e < i)
        {
            node res;
            res.inv = 0;
            return res;
        }
        if (b >= i && e <= j)
            return t[n];
        int mid = (b + e) >> 1, l = n << 1, r = l | 1;
        auto L = query(l, b, mid, i, j);
        auto R = query(r, mid + 1, e, i, j);
        return marge(L, R);
    }
} t;

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    t.build(1, 1, n);
    while (q--)
    {
        int ty;
        cin >> ty;
        if (ty == 1)
        {
            int l, r;
            cin >> l >> r;
            auto tt = t.query(1, 1, n, l, r);
            cout << t.query(1, 1, n, l, r).inv << '\n';
        }
        else
        {
            int i, x;
            cin >> i >> x;
            t.upd(1, 1, n, i, x);
            a[i] = x;
        }
    }
    return 0;
}