Shared code

#include<bits/stdc++.h>
using namespace std;
#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);
 
#ifndef ONLINE_JUDGE
#include "debug.cpp"
#else
#define debug(...)
#endif
 
const int MAX_N = 2e5 + 5;
#define lc (2 * id + 1)
#define rc (2 * id + 2)

int n, q, t[MAX_N << 2], a[MAX_N], nxt[MAX_N];
 
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;
    unordered_map<int, vector<int>> posVec;
    unordered_map<int, set<int>> pos;
    
    for(int i = 0; i < n; ++i){
        cin >> a[i];
        nxt[i] = n;
        if(!posVec[a[i]].empty()) nxt[posVec[a[i]].back()] = i;
        posVec[a[i]].push_back(i);
        pos[a[i]].insert(i);
    }
 
    build();
    while(q--){
        int t; cin >> t;
        if(t == 1){
            int k, u; cin >> k >> u;
            k--;
            if(a[k] == u) continue;
 
            auto it = pos[a[k]].find(k);
            if(it != pos[a[k]].begin()){
                nxt[*--it] = nxt[k];
                update(*it, nxt[*it]);
            }
            pos[a[k]].erase(k);
 
            it = pos[u].upper_bound(k);
            nxt[k] = (it == pos[u].end() ? n : *it);
            update(k, nxt[k]);
            if(it != pos[u].begin()){
                nxt[*--it] = k;
                update(*it, nxt[*it]);
            }
            pos[u].insert(k);
            a[k] = u;
        }
        else{
            int l, r; cin >> l >> r;
            l--, r--;
            if(get(l, r) > r) cout << "YES\n";
            else cout << "NO\n";
        }
    }
}
signed main(){
    IOS
    Heisenberg();
}