Juanzhang

#include <cstring>
#include <cstdio>
using namespace std;

const int maxn = 1e5 + 10;
int n, m, tot, val[maxn], ans[maxn];
int Q[maxn * 3], Q1[maxn * 3], Q2[maxn * 3];

struct BIT {
  int now, c[maxn], t[maxn];

  void clr() { ++now; }

  void add(int pos, int v) {
    for (; pos <= n; pos += pos & -pos) {
      t[pos] < now ? t[pos] = now, c[pos] = v : c[pos] += v;
    }
  }

  int query(int pos) {
    int res = 0;
    for (; pos; pos &= pos - 1) {
      res += t[pos] < now ? 0 : c[pos];
    }
    return res;
  }
} bit;

struct node {
  int x, y, k, tid;

  node() {}
  node(int _x, int _y, int _k, int _t) :
    x(_x), y(_y), k(_k), tid(_t) {}
} a[maxn * 3];

void divide(int l, int r, int ql, int qr) {
  if (l > r) return;
  if (ql == qr) {
    for (int i = l; i <= r; i++) {
      ans[a[Q[i]].tid] = ql;
    }
    return;
  }
  bit.clr();
  int mid = (ql + qr) >> 1, p1 = 0, p2 = 0;
  for (int i = l; i <= r; i++) {
    node &val = a[Q[i]];
    if (val.tid) {
      int s = bit.query(val.y) - bit.query(val.x - 1);
      val.k > s ? val.k -= s, Q2[++p2] = Q[i] : Q1[++p1] = Q[i];
    } else {
      val.y <= mid ? bit.add(val.x, val.k), Q1[++p1] = Q[i] : Q2[++p2] = Q[i];
    }
  }
  for (int i = 1; i <= p1; i++) {
    Q[l + i - 1] = Q1[i];
  }
  for (int i = 1; i <= p2; i++) {
    Q[r - p2 + i] = Q2[i];
  }
  divide(l, l + p1 - 1, ql, mid);
  divide(l + p1, r, mid + 1, qr);
}

int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", val + i);
    a[++tot] = node(i, val[i], 1, 0);
  }
  for (int i = 1; i <= m; i++) {
    char op; int x, y, k;
    scanf("%s %d %d", &op, &x, &y);
    if (op == 'C') {
      a[++tot] = node(x, val[x], -1, 0);
      a[++tot] = node(x, y, 1, 0), val[x] = y;
    } else {
      scanf("%d", &k);
      a[++tot] = node(x, y, k, i);
    }
  }
  memset(ans, -1, sizeof ans);
  for (int i = 1; i <= tot; i++) {
    Q[i] = i;
  }
  divide(1, tot, 1, 1e9);
  for (int i = 1; i <= m; i++) {
    if (~ans[i]) printf("%d\n", ans[i]);
  }
  return 0;
}