题意
给定一棵大小为 \(n\) 的 \(1\) 为根节点的树，树用如下方式给出：输入 \(a_2,a_3,\dots,a_n\)，保证 \(1\leq a_i<i\)，将 \(a_i\) 与 \(i\) 连边形成一棵树。
接下来有两种操作：
1 l r x令 \(a_i=\max(a_i-x,1)(l\leq i\leq r)\)。2 u v查询在当前的 \(a\) 数组构成的树上 \(u,v\) 的 LCA。
两种操作共有 \(q\) 个。
\(2\leq n,q\leq 10^5\)，\(2\leq l\leq r\leq n\)，\(1\leq x\leq 10^5\)，\(1\leq u,v\leq n\)
思路
根据题意，\(a_i\) 只会减小，且减小若干次后就会恒等于 \(1\)。考虑对原序列进行分块操作。设块的大小为 \(\sqrt{n}\)。
对于块内的每个元素，维护其祖先节点中最大的不在这个块内的节点 \(b_i\)。每次查询 \(LCA\) 的时候只需要用类似于树链剖分求 \(LCA\) 的操作来进行即可。这部分的时间复杂为 \(O(n\sqrt{n})\)。
对于 \(i\)，若 \(a_i\) 不在这个快内，那么直接令 \(b_i=a_i\)；否则令 \(b_i=b_{a_i}\)。
对于零散块每次直接暴力修改，对于整块，也可以直接重构。由于每次 \(a_i\) 至少减少 \(1\)，所以每个块至多被重构 \(\sqrt{n}\) 次，总的重构次数不会超过 \(O(\sqrt{n})\) 次。
code：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10,B=405;
int cnt[N],pos[N],L[B],R[B],n,m,a[N],b[N],tag[N];
void update(int x)
{
for(int i=L[x];i<=R[x];i++) a[i]=max(1,a[i]-tag[x]);tag[x]=0;
for(int i=L[x];i<=R[x];i++) if(a[i]<L[x]) b[i]=a[i];else b[i]=b[a[i]];
}
void change(int l,int r,int z)
{
if(pos[l]==pos[r])
{
for(int i=l;i<=r;i++) a[i]=max(1,a[i]-z);
update(pos[r]);return ;
}
for(int i=l;i<=R[pos[l]];i++) a[i]=max(1,a[i]-z);update(pos[l]);
for(int i=L[pos[r]];i<=r;i++) a[i]=max(1,a[i]-z);update(pos[r]);
for(int i=pos[l]+1;i<pos[r];i++)
{
tag[i]=min(tag[i]+z,n);
if(++cnt[i]<=B) update(i);
}
}
int realb(int x){return max(1,b[x]-tag[pos[x]]);}
//b[x]要么是x直接指向的，要么是x在块内的某个祖先指向的，所以一定也要减去区间内的减标记
int LCA(int x,int y)
{
while(1)
{
if(pos[x]<pos[y]) swap(x,y);
if(pos[x]!=pos[y]) x=realb(x);
else
{
if(realb(x)!=realb(y)) x=realb(x),y=realb(y);
else break;
}
}
while(x!=y)
{
if(x<y) swap(x,y);
x=max(1,a[x]-tag[pos[x]]);
}
return x;
}
int main()
{
scanf("%d%d",&n,&m);for(int i=2;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) pos[i]=(i-1)/B+1;
for(int i=1;i<=(n-1)/B+1;i++) L[i]=R[i-1]+1,R[i]=min(i*B,n),update(i);
while(m--)
{
int opt,x,y,z;scanf("%d%d%d",&opt,&x,&y);
if(opt==1) scanf("%d",&z),change(x,y,z);
else printf("%d\n",LCA(x,y));
}
return 0;
}