刚开始自己写了30分左右，后来看了解题说的，把零散块放一起了，但是也只能到50分，有没有人帮忙看看是复杂度不对还是常数问题，谢谢！

#define NDEBUG
#include <algorithm>
#include <cassert>
#include <cstring>
#include <functional>
#include <initializer_list>
#include <iostream>
#include <memory>
#include <random>
#include <vector>

struct IO {
  char a[1 << 25], *s;
  char b[1 << 25], *t;
  IO() : s(a), t(b) {
#ifdef LOCAL
    freopen("..\\in", "r", stdin), freopen("..\\out", "w", stdout);
#endif
    a[fread(a, 1, sizeof a, stdin)] = 0;
  }
  ~IO() { fwrite(b, 1, t - b, stdout); }
  template <typename T> IO &operator>>(T &x) {
    x = 0;
    bool flag = false;
    while (*s < '0' || *s > '9')
      if (*s++ == '-') flag = true;
    while (*s >= '0' && *s <= '9') x = x * 10 + *s++ - '0';
    if (flag) x = -x;
    return *this;
  }
  IO &operator<<(char x) { return *t++ = x, *this; }
  template <typename T> IO &operator<<(T x) {
    static char c[24];
    char *i = c;
    if (x == 0) {
      *t++ = '0';
    } else {
      if (x < 0) *t++ = '-', x *= -1;
      while (x) {
        T y = x / 10;
        *i++ = x - y * 10 + '0', x = y;
      }
      while (i != c) *t++ = *--i;
    }
    return *this;
  }
} io;

namespace test {

template <typename T> T my_abs(T x) { return x >= 0 ? x : -x; }

double my_sqrt(int x) { // x_1 = x_0 - f(x) / f'(x)
  double res = 1, tmp;
  while (my_abs(tmp = res * res - x) >= 0.1) res -= tmp / (res * 2.0);
  return res;
}

constexpr std::size_t N = 1e5 + 5;

int a[N], mp[N]; // 原数组和映射到 Block 中的下标
int n;           // 数组长度
int m;           // 询问次数

struct Block {
  int v, mp; // v=value,mp=对应a中的下标
} b[N];

struct BlockCmp {
public:
  bool operator()(const Block &lhs, const Block &rhs) const { return lhs.v < rhs.v; }
};

int blk_lazy[512];

int BLK_SIZE, BLK_TOT;

int which_block(int x) { return x / BLK_SIZE; }

int block_start(int x) { return x * BLK_SIZE; }

int block_end(int x) { return std::min(n, (x + 1) * BLK_SIZE); }

void init() {
  io >> n >> m;
  for (int i = 0; i != n; ++i) io >> a[i], b[i].v = a[i], b[i].mp = i;
  BLK_SIZE = 1.25 * my_sqrt(n), BLK_TOT = (n - 1) / BLK_SIZE + 1;
  // std::memset(blk_lazy, 0, sizeof blk_lazy);
  for (int i = 0; i != BLK_TOT; ++i) std::sort(b + block_start(i), b + block_end(i), BlockCmp());
  for (int i = 0; i != n; ++i) mp[b[i].mp] = i; // 反向映射
}

void merge(int belong /* which block */, const std::vector<bool> &marked) {
  std::vector<Block> bucket_a, bucket_b;
  for (int i = block_start(belong), e = block_end(belong); i != e; ++i) {
    if (!marked[i]) {
      bucket_a.push_back(b[i]);
    } else {
      bucket_b.push_back(b[i]);
    }
  }
  std::merge(bucket_a.begin(), bucket_a.end(), bucket_b.begin(), bucket_b.end(),
             b + block_start(belong), BlockCmp());
  for (int i = block_start(belong), e = block_end(belong); i != e; ++i) {
    mp[b[i].mp] = i;
  }
}

void modify(int l, int r, int k) { // [l, r] + k
  int left = which_block(l), right = which_block(r);
  std::vector<bool> tmp(n); // 存储修改的下标，用于归并两个有序的块
  if (left == right) {      // 在同一块中
    for (int i = l; i <= r; ++i) a[i] += k, b[mp[i]].v += k, tmp[mp[i]] = true;
    merge(left, tmp);
  } else {
    for (int i = l, e = block_end(left); i != e; ++i) a[i] += k, b[mp[i]].v += k, tmp[mp[i]] = true;
    merge(left, tmp);
    for (int i = left + 1; i < right; ++i) blk_lazy[i] += k;
    for (int i = block_start(right); i <= r; ++i) a[i] += k, b[mp[i]].v += k, tmp[mp[i]] = true;
    merge(right, tmp);
  }
}

int blk_piece[N];

int make_piece(int l, int r) { // 将散块整合成一块，可以二分
  int left = which_block(l), right = which_block(r);
  std::vector<bool> tmp(n);
  std::vector<int> bucket_a, bucket_b;
  int k = 0;
  if (left == right) { // 只有一块零散块
    for (int i = l; i <= r; ++i) tmp[mp[i]] = true;
    for (int i = block_start(left), e = block_end(left); i != e; ++i) {
      if (tmp[i]) blk_piece[k++] = b[i].v + blk_lazy[left];
    }
  } else { // 两块零散块
    for (int i = l, e = block_end(left); i != e; ++i) tmp[mp[i]] = true;
    for (int i = block_start(right); i <= r; ++i) tmp[mp[i]] = true;
    for (int i = block_start(left), e = block_end(left); i != e; ++i) {
      if (tmp[i]) bucket_a.push_back(b[i].v + blk_lazy[left]);
    }
    for (int i = block_start(right), e = block_end(right); i != e; ++i) {
      if (tmp[i]) bucket_b.push_back(b[i].v + blk_lazy[right]);
    }
    std::merge(bucket_a.begin(), bucket_a.end(), bucket_b.begin(), bucket_b.end(), blk_piece,
               std::less<>());
  }
  return bucket_a.size() + bucket_b.size() + k;
}

int query_piece(int lim, int k) {
  return std::lower_bound(blk_piece, blk_piece + lim, k) - blk_piece;
}

int query_whole(int l, int r, int k) { // 询问 [l, r] 有多少比 k 小的（整块）
  int ans1 = 0;
  int left = which_block(l), right = which_block(r);
  for (int i = left + 1; i < right; ++i)
    ans1 += std::lower_bound(b + block_start(i), b + block_end(i), Block{k - blk_lazy[i], 0},
                             BlockCmp()) -
            (b + block_start(i));
  return ans1;
}

int query(int l, int r, int lim, int k) { // 询问 [l, r] 有多少比 k 小的
  return query_piece(lim, k) + query_whole(l, r, k);
}

std::pair<int, int> query(int l, int r, int lim) {
  int ans1 = std::numeric_limits<int>::max(),
      ans2 = std::numeric_limits<int>::min(); // [ans1, ans2] 区间
  ans1 = std::min(ans1, blk_piece[0]);
  ans2 = std::max(ans2, blk_piece[lim - 1]);
  int left = which_block(l), right = which_block(r);
  for (int i = left + 1; i < right; ++i)
    ans1 = std::min(ans1, b[block_start(i)].v + blk_lazy[i]),
    ans2 = std::max(ans2, b[block_end(i) - 1].v + blk_lazy[i]);
  return {ans1, ans2};
}

} // namespace test
using namespace test;
using namespace std;

int main() {
  init();
  int cmd, l, r, v;
  while (m--) {
    io >> cmd >> l >> r >> v;
    if (cmd == 2) {
      modify(l - 1, r - 1, v);
    } else {
      if (r - l + 1 < v) {
        io << -1;
      } else {
        int mid;
        int lim = make_piece(l - 1, r - 1);
        auto [left, right] = query(l - 1, r - 1, lim);
        ++right;
        while (left < right) { // [left, right)
          mid = left + (right - left) / 2;
          int jj = query(l - 1, r - 1, lim,
                         mid); // 因为这里需要多次 query 所以需要把零散块合并起来一起二分，我傻逼了
          if (jj < v)
            left = mid + 1;
          else
            right = mid;
        }
        io << left-1 << '\n';
      }
    }
  }
  return 0;
}