我找到另一个题解了

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

const int MAXN    = 100000 + 5;
const int MAXQ    = 200000 + 5;
const int MAXNODE = MAXN + MAXQ;   
const int MAXOPS  = MAXNODE + 5;
const int MAXBLK  = 2048;          
const int BCAP    = 512;           
const int BTOP    = 1024;         
static char ibuf[1 << 20];
static int ipos = 0, iend = 0;
static inline int gc() {
    if (ipos == iend) {
        iend = (int)fread(ibuf, 1, sizeof ibuf, stdin);
        ipos = 0;
        if (!iend) return -1;
    }
    return ibuf[ipos++];
}
static inline int rd() {
    int c = gc();
    while (c != '-' && (c < '0' || c > '9')) { if (c == -1) return 0; c = gc(); }
    int s = 1;
    if (c == '-') { s = -1; c = gc(); }
    int x = 0;
    while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = gc(); }
    return x * s;
}
static char obuf[1 << 22];
static int opos = 0;
static inline void oflush() { if (opos) { fwrite(obuf, 1, opos, stdout); opos = 0; } }
static inline void oput(int x) {
    if (opos > (int)sizeof obuf - 24) oflush();
    char t[12]; int n = 0;
    if (x == 0) t[n++] = '0';
    else { if (x < 0) { obuf[opos++] = '-'; x = -x; } while (x) { t[n++] = char('0' + x % 10); x /= 10; } }
    while (n) obuf[opos++] = t[--n];
    obuf[opos++] = '\n';
}
static int N, Q;
static int opT[MAXQ], opX[MAXQ], opY[MAXQ], opZ[MAXQ];
static int insNode[MAXQ];          
static int qA[MAXQ], qB[MAXQ];   

static int rawVal[MAXNODE];        // 节点原始值
static int vIdx[MAXNODE];          // 节点值的压缩下标
static int vals[MAXNODE];          // 压缩后的值表
static int V;                      // 值域大小

static int firstChild[MAXNODE], nextSib[MAXNODE], lab[MAXNODE];
static int labelMax;

// ---------------- 块状链表（只用于离线模拟，维护节点编号序列）----------------
static int blk[MAXBLK][BCAP];
static int blen[MAXBLK];
static int ord[MAXBLK], nblk, nslot;
static int bitBlk[MAXBLK + 1];
static int totalLen;

static inline void rebuildBlkBit() {
    memset(bitBlk, 0, sizeof(int) * (MAXBLK + 1));
    for (int i = 0; i < nblk; i++) bitBlk[i + 1] = blen[ord[i]];
    for (int i = 1; i <= MAXBLK; i++) {
        int j = i + (i & -i);
        if (j <= MAXBLK) bitBlk[j] += bitBlk[i];
    }
}
static inline void addBlk(int i, int d) { for (; i <= MAXBLK; i += i & -i) bitBlk[i] += d; }

// 返回 pos（1-based）所在的顺序块下标，off 为块内偏移
static inline int findBlk(int pos, int &off) {
    int idx = 0, sum = 0;
    for (int b = BTOP; b; b >>= 1) {
        int nx = idx + b;
        if (nx <= MAXBLK && sum + bitBlk[nx] < pos) { idx = nx; sum += bitBlk[nx]; }
    }
    off = pos - sum - 1;
    return idx;
}
static inline int seqAt(int pos) {
    int off; int b = findBlk(pos, off);
    return blk[ord[b]][off];
}

static void repack();

static void splitBlk(int b) {
    if (nslot >= MAXBLK - 1) { repack(); if (b >= nblk) b = nblk - 1; }
    int s = ord[b];
    if (blen[s] < 2) return;
    int half = blen[s] >> 1;
    int ns = nslot++;
    blen[ns] = blen[s] - half;
    memcpy(blk[ns], blk[s] + half, sizeof(int) * blen[ns]);
    blen[s] = half;
    for (int i = nblk; i > b + 1; --i) ord[i] = ord[i - 1];
    ord[b + 1] = ns;
    nblk++;
    rebuildBlkBit();
}

static void repack() {
    static int tmp[MAXNODE];
    int cnt = 0;
    for (int i = 0; i < nblk; i++) { int s = ord[i]; for (int j = 0; j < blen[s]; j++) tmp[cnt++] = blk[s][j]; }
    nblk = 0; nslot = 0; totalLen = cnt;
    const int per = BCAP / 2;
    for (int i = 0; i < cnt; i += per) {
        int s = nslot++, c = min(per, cnt - i);
        ord[nblk++] = s; blen[s] = c;
        memcpy(blk[s], tmp + i, sizeof(int) * c);
    }
    if (!nblk) { nblk = 1; ord[0] = nslot++; blen[ord[0]] = 0; }
    rebuildBlkBit();
}

static void buildSeq(int n) {
    nblk = 0; nslot = 0; totalLen = n;
    const int per = BCAP * 3 / 4;
    for (int i = 0; i < n; i += per) {
        int s = nslot++, c = min(per, n - i);
        ord[nblk++] = s; blen[s] = c;
        for (int j = 0; j < c; j++) blk[s][j] = i + j + 1;   // 初始节点编号即位置
    }
    if (!nblk) { nblk = 1; ord[0] = nslot++; blen[ord[0]] = 0; }
    rebuildBlkBit();
}

// 在第 x 个元素之后插入（x=0 表示插到最前，x=totalLen 表示插到最后）
static void seqInsert(int x, int node) {
    if (!nblk) { nblk = 1; ord[0] = nslot++; blen[ord[0]] = 0; rebuildBlkBit(); }
    int b, off;
    if (x >= totalLen) { b = nblk - 1; off = blen[ord[b]]; }
    else               { b = findBlk(x + 1, off); }
    if (blen[ord[b]] == BCAP) {
        splitBlk(b);
        if (off >= blen[ord[b]]) { off -= blen[ord[b]]; b++; }
    }
    int s = ord[b], *p = blk[s];
    if (blen[s] > off) memmove(p + off + 1, p + off, sizeof(int) * (blen[s] - off));
    p[off] = node;
    blen[s]++; totalLen++; addBlk(b + 1, 1);
}

static void seqErase(int x) {
    if (totalLen <= 0) return;
    int off; int b = findBlk(x, off); int s = ord[b], *p = blk[s];
    if (off + 1 < blen[s]) memmove(p + off, p + off + 1, sizeof(int) * (blen[s] - off - 1));
    blen[s]--; totalLen--; addBlk(b + 1, -1);
}

// ---------------- DFS 标号 ----------------
struct Frame { int u, ch; };
static Frame stk[MAXNODE];

static void buildLabels() {
    int sp = 0; labelMax = 0;
    stk[sp].u = 0; stk[sp].ch = firstChild[0]; sp++;
    while (sp) {
        Frame &f = stk[sp - 1];
        if (!f.ch) { sp--; continue; }
        int u = f.ch;
        f.ch = nextSib[u];
        lab[u] = ++labelMax;
        stk[sp].u = u; stk[sp].ch = firstChild[u]; sp++;
    }
}

// ---------------- 整体二分 ----------------
struct Op { int a, b, c, d; };       // d<0 修改(a=标号,b=值下标,c=增量)；d>=0 询问(a=L,b=R,c=k,d=询问编号)
static Op bufA[MAXOPS], bufB[MAXOPS], tmpOp[MAXOPS];
static int bitArr[MAXNODE];
static int ansQ[MAXQ], nQuery;

static inline void badd(int i, int d) { const int n = labelMax; for (; i <= n; i += i & -i) bitArr[i] += d; }
static inline int  bsum(int i) { int s = 0; for (; i > 0; i -= i & -i) s += bitArr[i]; return s; }

static void solve(int vl, int vr, int lo, int hi, int buf) {
    if (lo >= hi) return;
    Op *src = buf ? bufB : bufA;
    Op *dst = buf ? bufA : bufB;
    if (vl == vr) {
        int v = vals[vl];
        for (int i = lo; i < hi; i++) if (src[i].d >= 0) ansQ[src[i].d] = v;
        return;
    }
    int mid = (vl + vr) >> 1;
    int nl = lo, nr = 0, ql = 0, qr = 0;
    for (int i = lo; i < hi; i++) {
        Op o = src[i];
        if (o.d < 0) {
            if (o.b <= mid) { badd(o.a, o.c); dst[nl++] = o; }
            else            { tmpOp[nr++] = o; }
        } else {
            int cnt = bsum(o.b) - bsum(o.a - 1);
            if (o.c <= cnt) { dst[nl++] = o; ql++; }
            else            { o.c -= cnt; tmpOp[nr++] = o; qr++; }
        }
    }
    for (int i = lo; i < nl; i++) if (dst[i].d < 0) badd(dst[i].a, -dst[i].c);   // 回滚
    if (nr) memcpy(dst + nl, tmpOp, sizeof(Op) * nr);
    int rStart = nl;
    if (ql) solve(vl, mid, lo, nl, buf ^ 1);
    if (qr) solve(mid + 1, vr, rStart, hi, buf ^ 1);
}

// ---------------- 主流程 ----------------
int main() {
    N = rd(); Q = rd();
    int nn = 0, vcnt = 0;
    for (int i = 1; i <= N; i++) { rawVal[++nn] = rd(); vals[vcnt++] = rawVal[nn]; }

    for (int j = 1; j <= Q; j++) {
        int t = rd(); opT[j] = t;
        if (t == 1)      { opX[j] = rd(); opY[j] = rd(); opZ[j] = rd(); }
        else if (t == 2) { opX[j] = rd(); opY[j] = rd(); insNode[j] = ++nn; rawVal[nn] = opY[j]; vals[vcnt++] = opY[j]; }
        else             { opX[j] = rd(); }
    }

    sort(vals, vals + vcnt);
    V = (int)(unique(vals, vals + vcnt) - vals);
    for (int i = 1; i <= nn; i++)
        vIdx[i] = (int)(lower_bound(vals, vals + V, rawVal[i]) - vals);

    // 离线模拟：只为了求出每个插入元素的前驱、每个询问两端的元素
    buildSeq(N);
    for (int i = N; i >= 1; i--) { nextSib[i] = firstChild[0]; firstChild[0] = i; }   // HEAD=0 的孩子按序为 1..N

    for (int j = 1; j <= Q; j++) {
        int t = opT[j];
        if (t == 1) {
            int l = opX[j], r = opY[j];
            if (l < 1) l = 1;
            if (r > totalLen) r = totalLen;
            if (l > r) l = r;
            qA[j] = seqAt(l); qB[j] = seqAt(r);
        } else if (t == 2) {
            int x = opX[j], nd = insNode[j];
            if (x < 0) x = 0;
            if (x > totalLen) x = totalLen;
            int pred = (x == 0) ? 0 : seqAt(x);
            nextSib[nd] = firstChild[pred];
            firstChild[pred] = nd;             // 后插入的排在前驱孩子的最前面
            seqInsert(x, nd);
        } else {
            int x = opX[j];
            if (totalLen <= 0) { opT[j] = 0; continue; }   // 空序列上的删除，忽略
            if (x < 1) x = 1;
            if (x > totalLen) x = totalLen;
            qA[j] = seqAt(x);
            seqErase(x);
        }
    }

    buildLabels();

    int nop = 0;
    for (int i = 1; i <= N; i++) {
        Op &o = bufA[nop++]; o.a = lab[i]; o.b = vIdx[i]; o.c = 1; o.d = -1;
    }
    nQuery = 0;
    for (int j = 1; j <= Q; j++) {
        if (opT[j] == 1) {
            int L = lab[qA[j]], R = lab[qB[j]];
            if (L > R) { int t = L; L = R; R = t; }
            int k = opZ[j];
            if (k < 1) k = 1;
            if (k > R - L + 1) k = R - L + 1;
            Op &o = bufA[nop++]; o.a = L; o.b = R; o.c = k; o.d = nQuery++;
        } else if (opT[j] == 2) {
            int nd = insNode[j];
            Op &o = bufA[nop++]; o.a = lab[nd]; o.b = vIdx[nd]; o.c = 1; o.d = -1;
        } else if (opT[j] == 3) {
            int nd = qA[j];
            Op &o = bufA[nop++]; o.a = lab[nd]; o.b = vIdx[nd]; o.c = -1; o.d = -1;
        }
    }

    solve(0, V - 1, 0, nop, 0);

    for (int i = 0; i < nQuery; i++) oput(ansQ[i]);
    oflush();
    return 0;
}