题单中唯一一道黑题，但是挺套路的，类似于弹飞绵羊。

把 $a$ 序列分成 $\sqrt n$ 段，对每个数记录它第一次跳出块是跳到哪里 $pre_i$。
修改：对于零散段，暴力计算 $a$，暴力把整段重构；对于大块，直接打个标记记录整体要减多少，再根据情况看是否要暴力重构。
观察到一个段只要减去了 $\geq \sqrt n$ 次就一定有 $pre_i = a_i$，所以此时就不需要暴力重构。

查询就类似重链剖分往上跳。

这里放的是 双倍经验 的代码。

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void read(T &x){
    x=0;int f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    x*=f;
}
template<typename T,typename ... Args>
void read(T &x, Args &... y){read(x);read(y...);}

const int N = 4e5 + 15;
int n, q, B, a[N], pre[N];
int pos[N];

int m, l[N], r[N], flag[N], cnt[N];

inline int del(int x, int d) { return max(x - d, 1); }
inline void init() {
    for (int i = 1; i * B <= n; i++) ++m, l[m] = r[m - 1] + 1, r[m] = i * B;
    if (m * B < n) ++m, l[m] = r[m - 1] + 1, r[m] = n;

    for (int i = 1; i <= m; i++)
        for (int j = l[i]; j <= r[i]; j++) pos[j] = i;
}
inline void build(int u) {
    if (flag[u])
        for (int i = l[u]; i <= r[u]; i++) a[i] = del(a[i], flag[u]);
    flag[u] = 0;
    for (int i = l[u]; i <= r[u]; i++) pre[i] = (a[i] < l[u]) ? a[i] : pre[a[i]];
}

inline void change(int x, int y, int d) {
    if (pos[x] == pos[y]) {
        for (int i = x; i <= y; i++) a[i] = del(a[i], d);
        build(pos[x]);
        return;
    }
    for (int i = x; i <= r[pos[x]]; i++) a[i] = del(a[i], d);
    for (int i = l[pos[y]]; i <= y; i++) a[i] = del(a[i], d);
    build(pos[x]), build(pos[y]);

    for (int u = pos[x] + 1; u <= pos[y] - 1; u++) {
        flag[u] = min(flag[u] + d, n);
        if (cnt[u] <= B) build(u);  //更新次数较少，暴力重构
        cnt[u] = min(cnt[u] + d, n);
    }
}

inline int lca(int x, int y) {
    while (1) {
        if (pos[x] < pos[y]) swap(x, y);
        int fx = del(pre[x], flag[pos[x]]), fy = del(pre[y], flag[pos[y]]);
        if (pos[x] > pos[y]) x = fx;
        else if (fx != fy) x = fx, y = fy;
        else break;
    }
    while (x != y) {
        if (x < y) swap(x, y);
        x = del(a[x], flag[pos[x]]);
    }
    return x;
}

int main() {
    read(n, q), B = 500;
    init();
    for (int i = 2; i <= n; i++) read(a[i]);
    for (int i = 1; i <= m; i++) build(i);
    int lst = 0;
    while (q--) {
        int opt; read(opt);
        if (opt == 1) {
            int l, r, x; read(l, r, x);
            l ^= lst, r ^= lst, x ^= lst;
            change(l, r, x);
        } else {
            int u, v; read(u, v);
            u ^= lst, v ^= lst;
            lst = lca(u, v);
            printf("%d\n", lst);
        }
    }
    return 0;
}