Untitled

#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>

#include <bits/stdc++.h>

#define all(c) c.begin(), c.end()
#define MOD((int) 1e9 + 7)

using namespace __gnu_pbds;
using namespace std;

typedef tree < int, int, less < int > , rb_tree_tag, tree_order_statistics_node_update > ost;
typedef tuple < int, int, int > iii;
typedef vector < int > vi;
typedef long long ll;

class SegmentTree {
    private: int n;
    vi st;
    int l(int p) {
        return p << 1;
    }
    int r(int p) {
        return (p << 1) + 1;
    }

    ll mod(ll a) {
        a %= MOD;
        return a < 0 ? a + MOD : a;
    }

    int conquer(int a, int b) {
        return (int) mod(mod((ll) a) * mod((ll) b));
    }

    int query(int p, int L, int R, int i, int j) {
        if (i > j)
            return 1;
        if ((L >= i) && (R <= j))
            return st[p];
        int m = (L + R) / 2;
        return conquer(query(l(p), L, m, i, min(m, j)),
            query(r(p), m + 1, R, max(i, m + 1), j));
    }

    void update(int p, int L, int R, int i, int j, int val) {
        if (i > j)
            return;
        if ((L >= i) && (R <= j))
            st[p] = val;
        else {
            int m = (L + R) / 2;
            update(l(p), L, m, i, min(m, j), val);
            update(r(p), m + 1, R, max(i, m + 1), j, val);
            st[p] = conquer(st[l(p)], st[r(p)]);
        }
    }

    public: SegmentTree(int sz): n(sz),
    st(4 * n, 0) {}
    void update(int i, int val) {
        update(1, 0, n - 1, i, i, val);
    }
    int query(int i, int j) {
        return query(1, 0, n - 1, i, j);
    }
    int pquery(int i) {
        return query(1, 0, n - 1, i, i);
    }
};

int main() {
    int t, n, q;
    scanf("%d", & t);

    while (t-- && scanf("%d%d", & n, & q)) {
        ost map;
        vi vn(n);
        int T, l, r;
        vector < iii > vq;

        for (auto & val: vn) {
            scanf("%d", & val);
            ++map[val];
        }

        while (q-- && scanf("%d%d%d", & T, & l, & r)) {
            if (T == 1) {
                l--;
                map[r] = map[r];
            }
            vq.push_back({
                T,
                l,
                r
            });
        }

        int i = 0;
        SegmentTree st(map.size());

        for (auto[_, val]: map)
            st.update(i++, val);

        auto plusX = [ & st](int v, int x) {
            st.update(v, st.pquery(v) + x);
        };

        for (auto[T, l, r]: vq) {
            if (T == 1) {
                plusX(map.order_of_key(vn[l]), -1);
                vn[l] = r;
                plusX(map.order_of_key(vn[l]), 1);
            } else {
                int L = map.order_of_key(l), R = map.order_of_key(r);
                if (map.find(l) == map.end() || map.find(r) == map.end() || (R - L) != (r - l))
                    printf("0\n");
                else
                    printf("%d\n", st.query(L, R));
            }
        }
    }

    return 0;
}