时间复杂度是 $O(\dfrac{n^2}{w})$，在 C++20 上 RE on #30，做法是对每个块维护 bitset。

#include<bits/stdc++.h>
using namespace std;
inline char gc(){
    static char buf[1000010],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000010,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x){
    x=0;
    static char s=gc();
    while(s<'0'||s>'9') s=gc();
    while(s>='0'&&s<='9') x=(x<<3)+(x<<1)+(s^48),s=gc();
}
static char buf[1000001];
int len=-1;
inline void flush(){
    fwrite(buf,1,len+1,stdout);
    len=-1;
}
inline void __PC(const char x){
    if(len==1000000) flush();
    buf[++len]=x;
}
inline void write(int x){
    if(x>9) write(x/10);
    __PC(x%10^48);
}
const int N=4e5+10;
bitset<640> b[N],vis[N];
int n,q,a[N],block[N],L[N],R[N],B,tot,tag[N],mx[N],to[N];
inline void rebuild(const int p){
	mx[p]=INT_MIN;
	for(int i=L[p];i<=R[p];++i) a[i]=max(1,a[i]-tag[p]);
	tag[p]=0;
	for(int i=L[p];i<=R[p];++i){
		b[i].reset(),b[i][i-L[p]]=1;
		if(block[a[i]]==block[i]) b[i]|=b[a[i]],to[i]=to[a[i]];
		else to[i]=a[i];
		mx[p]=max(mx[p],a[i]);
	}
}
inline void update(const int l,const int r,const int x){
	if(block[l]==block[r]){
		for(int i=l;i<=r;++i) a[i]=max(1,a[i]-x);
		rebuild(block[l]);
	} else{
		for(int i=l;i<=R[block[l]];++i) a[i]=max(1,a[i]-x);
		rebuild(block[l]);
		for(int i=L[block[r]];i<=r;++i) a[i]=max(1,a[i]-x);
		rebuild(block[r]);
		for(int i=block[l]+1;i<block[r];++i){
			tag[i]+=x;
			if(mx[i]>=L[i]) rebuild(i);
		}
	}
}
inline void query(int u,int v){
	for(int i=1;i<=tot;++i) vis[i].reset();
	while(1){
		vis[block[u]]=b[u];
		if(block[u]==1) break;
		u=max(1,to[u]-tag[block[u]]);
	}
	while(1){
		if((vis[block[v]]&b[v]).any()){
			while(v){
				if(vis[block[v]][v-L[block[v]]]){
					write(v),__PC('\n');
					return;
				}
				if(v==1) break;
				v=max(1,a[v]-tag[block[v]]);
			}
		}
		v=max(1,to[v]-tag[block[v]]);
	}
}
signed int main(){
	read(n),read(q);
	a[1]=1;
	for(int i=2;i<=n;++i) read(a[i]);
	B=sqrt(n),tot=(n+B-1)/B;
	for(int i=1;i<=tot;++i){
		L[i]=(i-1)*B+1,R[i]=min(i*B,n);
		for(int j=L[i];j<=R[i];++j) block[j]=i;
	}
	for(int i=1;i<=tot;++i) rebuild(i);
	while(q--){
		int op,l,r,x;
		read(op),read(l),read(r);
		if(op==1) read(x),update(l,r,x);
		else query(l,r);
	}
	flush();
	return 0;
}