代码：

#include<bits/stdc++.h>

#define endl '\n';
#define rnd() rand()

using namespace std;

const int N = 2e5 + 5;
const int M = 1e7 + 5;

int n, m;
int a[N];

int tot;

struct Node{
  int ls, rs;
  int val, key;
  int size;
}tree[M];

struct FHQ_Treap{
  int root;

  inline int newnode(int val){
    tot++;
    tree[tot].val = val;
    tree[tot].ls = 0;
    tree[tot].rs = 0;
    tree[tot].key = rnd();
    tree[tot].size = 1;
    return tot;
  }

  inline void update(int node){
    tree[node].size = tree[tree[node].ls].size + tree[tree[node].rs].size + 1;
  }

  void split(int node, int val, int &r1, int &r2){
    if(!node){
      r1 = r2 = 0;
      return ;
    }
    if(tree[node].val <= val){
      r1 = node;
      split(tree[node].rs, val, tree[node].rs, r2);
    }
    else{
      r2 = node;
      split(tree[node].ls, val, r1, tree[node].ls);
    }
    update(node);
  }

  int merge(int x, int y){
    if(!x || !y){
      return x + y;
    }
    if(tree[x].key < tree[y].key){
      tree[x].rs = merge(tree[x].rs, y);
      update(x);
      return x;
    }
    else{
      tree[y].ls = merge(x, tree[y].ls);
      update(y);
      return y;
    }
  }

  int t1, t2, t3;

  inline void insert(int val){
    split(root, val, t1, t2);
    root = merge(merge(t1, newnode(val)), t2);
  }

  inline void _delete(int val){
    split(root, val, t1, t3);
    split(t1, val - 1, t1, t2);
    t2 = merge(tree[t2].ls, tree[t2].rs);
    root = merge(merge(t1, t2), t3);
  }

  inline int rank_(int val){
    split(root, val - 1, t1, t2);
    int ans = tree[t1].size + 1;
    root = merge(t1, t2);
    cout << t1 << " " << t2;
    return ans;
  }

  inline int query(int rank){
    int node = root;
    while(node){
      if(tree[tree[node].ls].size + 1 == rank){
        break;
      }
      else if(tree[tree[node].ls].size >= rank){
        node = tree[node].ls;
      }
      else{
        rank -= tree[tree[node].ls].size + 1;
        node = tree[node].rs;
      }
    }
    return tree[node].val;
  }

  inline int pre(int val){
    split(root, val - 1, t1, t2);
    int node = t1;
    while(tree[node].rs){
      node = tree[node].rs;
    }
    int ans = (!tree[t1].size ? -2147483647 : tree[node].val);
    root = merge(t1, t2);
    return ans;
  }

  inline int nxt(int val){
    split(root, val, t1, t2);
    int node = t2;
    while(tree[node].ls){
      node = tree[node].ls;
    }
    int ans = (!tree[t2].size ? 2147483647 : tree[node].val);
    root = merge(t1, t2);
    return ans;
  }

  inline void build(int l, int r){
    for(int i = l; i <= r; i++){
      insert(a[i]);
    }
  }
}ft[N];

struct Segment_Tree{
  void build(int node, int lt, int rt){
    ft[node].build(lt, rt);
    if(lt == rt){
      return ;
    }
    int mid = lt + rt >> 1;
    build(node << 1, lt, mid);
    build(node << 1 | 1, mid + 1, rt);
  }

  int _rank(int node, int lt, int rt, int x, int y, int val){
    if(y < lt || x > rt){
      return 0;
    }
    if(x <= lt && rt <= y){
      return ft[node].rank_(val) - 1;
    }
    int mid = lt + rt >> 1;
    return _rank(node << 1, lt, mid, x, y, val) + _rank(node << 1 | 1, mid + 1, rt, x, y, val);
  }

  inline int query(int x, int y, int rak){
    int l = 0, r = 1e8, ans = -1;
    while(l <= r){
      int mid = l + r >> 1;
      if(_rank(1, 1, n, l, r, mid) + 1 <= rak){
        ans = mid, l = mid + 1;
      }
      else{
        r = mid - 1;
      }
    }
    return ans;
  }

  void update(int node, int lt, int rt, int x, int val){
    if(x < lt || x > rt){
      return ;
    }
    ft[node]._delete(a[x]);
    ft[node].insert(val);
    if(lt == rt && lt == x){
      return ;
    }
    int mid = lt + rt >> 1;
    update(node << 1, lt, mid, x, val);
    update(node << 1 | 1, mid + 1, rt, x, val);
  }

  inline int pre(int node, int lt, int rt, int x, int y, int val){
    if(y < lt || x > rt){
      return -2147483647;
    }
    if(x <= lt && rt <= y){
      return ft[node].pre(val);
    }
    int mid = lt + rt >> 1;
    return max(pre(node << 1, lt, mid, x, y, val), pre(node << 1 | 1, mid + 1, rt, x, y, val));
  }
  
  inline int nxt(int node, int lt, int rt, int x, int y, int val){
    if(y < lt || x > rt){
      return 2147483647;
    }
    if(x <= lt && rt <= y){
      return ft[node].nxt(val);
    }
    int mid = lt + rt >> 1;
    return min(nxt(node << 1, lt, mid, x, y, val), nxt(node << 1 | 1, mid + 1, rt, x, y, val));
  }
}T;

void Solve(){
  cin >> n >> m;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  T.build(1, 1, n);
  while(m--){
    int op;
    cin >> op;
    if(op == 1){
      int l, r, k;
      cin >> l >> r >> k;
      cout << T._rank(1, 1, n, l, r, k) + 1 << '\n';
    }
    else if(op == 2){
      int l, r, k;
      cin >> l >> r >> k;
      cout << T.query(l, r, k) << '\n';
    }
    else if(op == 3){
      int x, k;
      cin >> x >> k;
      T.update(1, 1, n, x, k);
      a[x] = k;
    }
    else if(op == 4){
      int l, r, k;
      cin >> l >> r >> k;
      cout << T.pre(1, 1, n, l, r, k) << '\n';
    }
    else{
      int l, r, k;
      cin >> l >> r >> k;
      cout << T.nxt(1, 1, n, l, r, k) << '\n';
    }
  }
}

signed main(){
  Solve();
  return 0;
}