Shared code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define ii pair<int, int>
#define nl '\n'
#define all(v) ((v).begin()), ((v).end())
#define sz(v) (int)((v).size())
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

const ll inf = 1e16;
const int mod = 1e9 + 7;

#ifndef ONLINE_JUDGE
#include "debug.cpp"
#else
#define debug(...)
#endif

#define lc (2 * id + 1)
#define rc (2 * id + 2)

int n, q;
vector<int> t, a, nxt;

void build(int id = 0, int l = 0, int r = n - 1){
    if(l == r){
        t[id] = nxt[l];
        return;
    }
    int m = (l + r) >> 1;
    build(lc, l, m);
    build(rc, m + 1, r);
    t[id] = min(t[lc], t[rc]);
}
void update(int p, int v, int id = 0, int l = 0, int r = n - 1){
    if(l == r){
        t[id] = v;
        return;
    }
    int m = (l + r) >> 1;
    if(p <= m) update(p, v, lc, l, m);
    else update(p, v, rc, m + 1, r);
    t[id] = min(t[lc], t[rc]);
}
int get(int lq, int rq, int id = 0, int l = 0, int r = n - 1){
    if(r < lq || rq < l) return n;
    if(lq <= l && r <= rq) return t[id];
    int m = (l + r) >> 1;
    return min(get(lq, rq, lc, l, m), get(lq, rq, rc, m + 1, r));
}

void Heisenberg(){
    cin >> n >> q;
    t.resize(4 * n + 10), a.resize(n), nxt.resize(n);
    vector<set<int>> pos;
    vector<array<int, 3>> que(q);
    
    for(auto &e: a) cin >> e;
    for(auto &e: que) cin >> e[0] >> e[1] >> e[2];
    
    vector<int> coordComp;
    unordered_map<int, int> mp;
    for(auto &e: a) coordComp.push_back(e);
    for(auto &e: que) if(e[0] == 1) coordComp.push_back(e[2]);

    sort(all(coordComp));
    coordComp.erase(unique(all(coordComp)), coordComp.end());
    pos.resize(sz(coordComp));
    for(int i = 0; i < sz(coordComp); ++i) mp[coordComp[i]] = i;

    for(int i = 0; i < n; ++i){
        a[i] = mp[a[i]], nxt[i] = n;
        if(!pos[a[i]].empty()) nxt[*--pos[a[i]].end()] = i;
        pos[a[i]].insert(i);
    }

    build();
    for(auto &e: que){
        if(e[0] == 1){
            auto &[t, k, u] = e;
            k--, u = mp[u];

            auto it = pos[a[k]].find(k);
            if(it != pos[a[k]].begin()){
                auto it1 = it; --it1;
                auto it2 = it; ++it2;
                nxt[*it1] = (it2 == pos[a[k]].end() ? n : *it2);
                update(*it1, nxt[*it1]);
            }
            pos[a[k]].erase(it);

            it = pos[u].upper_bound(k);
            nxt[k] = (it == pos[u].end() ? n : *it);
            update(k, nxt[k]);
            if(it != pos[u].begin()){
                auto it1 = it; --it1;
                nxt[*it1] = k;
                update(*it1, nxt[*it1]);
            }
            pos[u].insert(k);
            a[k] = u;
        }
        else{
            auto &[t, l, r] = e;
            l--, r--;
            if(get(l, r) > r) cout << "YES\n";
            else cout << "NO\n";
        }
    }
}
signed main(){
    IOS
    Heisenberg();
}