Shared code

#include <algorithm>
#include <functional>
#include <iostream>
#include <set>
#include <vector>

template <typename T> class SegmentTree {
public:
  int n;
  T idt;
  std::vector<T> seg;
  std::function<T(T, T)> f;

  SegmentTree(int n, std::function<T(T, T)> f = std::plus<T>(), T idt = T()) : n(n), idt(idt), f(f), seg(2 * n, idt) {}

  void set(int idx, T x) {
    for (seg[idx += n] = x, idx /= 2; idx > 0; idx /= 2) {
      seg[idx] = f(seg[2 * idx], seg[2 * idx + 1]);
    }
  }

  T query(int l, int r) {
    T ansL = idt, ansR = idt;
    for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
      if (l & 1) ansL = f(ansL, seg[l++]);
      if (r & 1) ansR = f(seg[--r], ansR);
    }
    return f(ansL, ansR);
  }

  T &operator[](int i) { return seg[n + i]; }
};

int main() {
  const int inf = 1e9;

  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  std::vector<int> buf;

  int n, q;
  std::cin >> n >> q;
  std::vector<int> a(n);
  for (auto &i : a) {
    std::cin >> i;
    buf.push_back(i);
  }
  struct Query {
    int t, a, b;
  };
  std::vector<Query> queries(q);
  for (auto &[t, a, b] : queries) {
    std::cin >> t >> a >> b;
    --a;
    if (t == 1) {
      buf.push_back(b);
    } else {
      --b;
    }
  }
  std::sort(buf.begin(), buf.end());
  buf.erase(std::unique(buf.begin(), buf.end()), buf.end());
  auto compress = [&](int x) {
    return std::lower_bound(buf.begin(), buf.end(), x) - buf.begin();
  };
  for (auto &i : a) {
    i = compress(i);
  }
  for (auto &[t, a, b] : queries) {
    if (t == 1) {
      b = compress(b);
    }
  }
  std::vector<std::set<int>> idx(n + q);
  for (int i = 0; i < n; ++i) {
    idx[a[i]].insert(i);
  }
  SegmentTree<int> st(n, [](int a, int b) {
    return std::min(a, b);
  }, inf);
  for (int i = 0; i < n; ++i) {
    auto it = idx[a[i]].lower_bound(i);
    if (it == --idx[a[i]].end()) {
      st.set(i, n);
    } else {
      st.set(i, *++it);
    }
  }

  for (auto &[t, u, v] : queries) {
    if (t == 1) {
      auto it1 = idx[a[u]].find(u);
      if (it1 != idx[a[u]].begin()) {
        st.set(*--it1, st[u]);
      }
      idx[a[u]].erase(it1);
      a[u] = v;
      auto it2 = idx[v].insert(u).first;
      if (it2 == idx[v].begin()) {
        if (it2 == --idx[v].end()) {
          st.set(u, n);
        } else {
          st.set(u, *++it2);
        }
      } else {
        st.set(u, st[*--it2]);
        st.set(*it2, u);
      }
    } else {
      std::cout << (st.query(u, v) > v ? "YES" : "NO") << '\n';
    }
  }
}