RT

#include <bits/stdc++.h>
//#pragma GCC optimize(3)
#define int long long
#define ri register
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define is insert
#define es erase
using namespace std;
const int N = 200010;
inline int read()
{
    int s = 0, w = 1;
    ri char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        s = (s << 3) + (s << 1) + (ch ^ 48), ch = getchar();
    return s * w;
}
int n, m, a[N], ta[N], pp, tb[N];
struct Query
{
    int x, y, k, opt, id;
} q[N], tmp[N], q1[N], q2[N];
int cnt, Ans[N], sum[N << 2], mx[N << 2];
#define lc (x << 1)
#define rc (x << 1 | 1)
inline void Push_Up(int x)
{
    sum[x] = sum[lc] + sum[rc];
    mx[x] = max(mx[lc], mx[rc]);
}
void UpDate(int pos, int l, int r, int x, int k1, int k2)
{
    if (l == r)
    {
        mx[x] = max(mx[x], k1);
        sum[x] += k2;
        return;
    }
    int mid = (l + r) / 2;
    if (pos <= mid)
        UpDate(pos, l, mid, lc, k1, k2);
    else
        UpDate(pos, mid + 1, r, rc, k1, k2);
    Push_Up(x);
}
int AskS(int u, int v, int l, int r, int x)
{
    if (l >= u && r <= v)
        return sum[x];
    int mid = (l + r) / 2, tt = 0;
    if (u <= mid)
        tt += AskS(u, v, l, mid, lc);
    if (v > mid)
        tt += AskS(u, v, mid + 1, r, rc);
    return tt;
}
int AskMx(int u, int v, int l, int r, int x)
{
    if (l >= u && r <= v)
        return mx[x];
    int mid = (l + r) / 2, tt = -2147483647;
    if (u <= mid)
        tt = max(tt, AskMx(u, v, l, mid, lc));
    if (v > mid)
        tt = max(tt, AskMx(u, v, mid + 1, r, rc));
    return tt;
}
void Renew(int pos, int l, int r, int x)
{
    if (l == r)
    {
        sum[x] = 0;
        mx[x] = -2147483647;
        return;
    }
    int mid = (l + r) / 2;
    if (pos <= mid)
        Renew(pos, l, mid, lc);
    else
        Renew(pos, mid + 1, r, rc);
    sum[x] = 0;
    mx[x] = -2147483647;
}
#undef lc
#undef rc
void Solvep(int u, int v, int l, int r)
{
    if (u > v || l > r)
        return;
    if (l == r)
    {
        for (ri int i = u; i <= v; i++)
            if (q[i].opt == 2)
                Ans[q[i].id] = tb[l];
        return;
    }
    int mid = (l + r) / 2;
    int tot1, tot2;
    tot1 = tot2 = 0;
    for (ri int i = u; i <= v; i++)
    {
        if (q[i].opt == 1)
        {
            if (q[i].k <= mid)
                q1[++tot1] = q[i];
            else
            {
                Ans[q[i].id] += AskS(q[i].x, q[i].y, 1, n, 1);
                q2[++tot2] = q[i];
            }
        }
        else if (q[i].opt == 2)
        {
            int gt = AskS(q[i].x, q[i].y, 1, n, 1);
            if (q[i].k <= gt)
                q1[++tot1] = q[i];
            else
            {
                q[i].k -= gt;
                q2[++tot2] = q[i];
            }
        }
        else if (q[i].opt == 3)
        {
            if (q[i].y <= mid)
            {
                q1[++tot1] = q[i];
                UpDate(q[i].x, 1, n, 1, q[i].y, q[i].k);
            }
            else
                q2[++tot2] = q[i];
        }
        else if (q[i].opt == 4)
        {
            if (q[i].k <= mid)
                q1[++tot1] = q[i];
            else
            {
                int num = AskMx(q[i].x, q[i].y, 1, n, 1);
                if (num >= 0)
                    Ans[q[i].id] = max(Ans[q[i].id], tb[num]);
                q2[++tot2] = q[i];
            }
        }
        else
            q1[++tot1] = q[i];
    }
    for (ri int i = 1; i <= tot1; i++)
    {
        q[u + i - 1] = q1[i];
        if (q1[i].opt == 3)
            Renew(q1[i].x, 1, n, 1);
    }
    for (ri int i = 1; i <= tot2; i++)
        q[u + tot1 + i - 1] = q2[i];
    Solvep(u, u + tot1 - 1, l, mid);
    Solvep(u + tot1, v, mid + 1, r);
}
void Solven(int u, int v, int l, int r)
{
    if (u > v || l >= r)
        return;
    int mid = (l + r) / 2;
    int tot1, tot2;
    tot1 = tot2 = 0;
    for (ri int i = u; i <= v; i++)
    {
        if (q[i].opt == 3)
        {
            if (q[i].y <= mid)
            {
                q1[++tot1] = q[i];
                UpDate(q[i].x, 1, n, 1, q[i].y, q[i].k);
            }
            else
                q2[++tot2] = q[i];
        }
        else if (q[i].opt == 5)
        {
            if (q[i].k <= mid)
                q1[++tot1] = q[i];
            else
            {
                q2[++tot2] = q[i];
                int num = AskMx(q[i].x, q[i].y, 1, n, 1);
                if (num >= 0)
                    Ans[q[i].id] = min(Ans[q[i].id], tb[pp + 1 - num]);
            }
        }
        else
            q1[++tot1] = q[i];
    }
    for (ri int i = 1; i <= tot1; i++)
    {
        q[u + i - 1] = q1[i];
        if (q1[i].opt == 3)
            Renew(q1[i].x, 1, n, 1);
    }
    for (ri int i = 1; i <= tot2; i++)
        q[u + tot1 + i - 1] = q2[i];
    Solven(u, u + tot1 - 1, l, mid);
    Solven(u + tot1, v, mid + 1, r);
}
signed main()
{
    n = read(), m = read();
    for (ri int i = 0; i < (N << 2); i++)
        mx[i] = -2147483647;
    for (ri int i = 1; i <= n; i++)
    {
        a[i] = ta[++pp] = read();
        cnt++, q[cnt] = (Query){i, a[i], 1, 3, cnt}, Ans[cnt] = -1;
    }
    for (ri int i = 1; i <= m; i++)
    {
        int opt, x, y;
        opt = read(), x = read(), y = read();
        if (opt != 3)
        {
            int k = read();
            ta[++pp] = k;
            cnt++, q[cnt] = (Query){x, y, k, opt, cnt};
            if (opt == 4)
                Ans[cnt] = -2147483647;
            else if (opt == 5)
                Ans[cnt] = 2147483647;
            if (opt == 1)
                Ans[cnt] = 1;
        }
        else
        {
            cnt++, q[cnt] = (Query){x, a[x], -1, 3, cnt}, Ans[cnt] = -1;
            cnt++, q[cnt] = (Query){x, y, 1, 3, cnt}, Ans[cnt] = -1;
            a[x] = y, ta[++pp] = y;
        }
    }
    sort(ta + 1, ta + 1 + pp);
    pp = unique(ta + 1, ta + 1 + pp) - ta - 1;
    for (ri int i = 1; i <= cnt; i++)
    {
        if (q[i].opt == 3)
        {
            int x = q[i].y;
            q[i].y = lower_bound(ta + 1, ta + 1 + pp, q[i].y) - ta;
            tb[q[i].y] = x;
        }
        else if (q[i].opt != 2)
        {
            int x = q[i].k;
            q[i].k = lower_bound(ta + 1, ta + 1 + pp, q[i].k) - ta;
            tb[q[i].k] = x;
        }
    }
    for (ri int i = 1; i <= cnt; i++)
        tmp[i] = q[i];
    Solvep(1, cnt, 1, pp);
    for (ri int i = 1; i <= cnt; i++)
    {
        q[i] = tmp[i];
        if (q[i].opt == 3)
            q[i].y = pp + 1 - q[i].y;
        else if (q[i].opt != 2)
            q[i].k = pp + 1 - q[i].k;
    }
    Solven(1, cnt, 1, pp);
    for (ri int i = 1; i <= cnt; i++)
        if (~Ans[i])
            printf("%lld\n", Ans[i]);
    return 0;
}

前趋和后继分开做...