题目描述
给定一棵大小为 \(n\) 的 \(1\) 为根节点的树，树用如下方式给出：输入 \(a_2,a_3,\dots,a_n\)，保证 \(1\leq a_i<i\)，将 \(a_i\) 与 \(i\) 连边形成一棵树。
接下来有 \(m\) 次操作，操作有两种：
1 l r x令 \(a_i=\max(a_i-x,1)(l\leq i\leq r)\)。2 u v查询在当前的 \(a\) 数组构成的树上 \(u,v\) 的 LCA。
输入格式
第一行包含两个数 \(n\)，\(m\)。
之后一行 \(n-1\) 个数，表示 \(a_2,...,a_n\)。
之后 \(m\) 行，每行三个或四个数，表示一次操作。
本题强制在线，所有输入的 \(l,r,x,u,v\) 均需要异或 \(lastans\)，其定义为上一次询问操作得到的答案，若之前没有询问操作，则为 \(0\)。
输出格式
对于每个 \(2\) 操作，输出一行一个数表示答案。
样例 #1
样例输入 #1
6 4
1 2 3 3 4
2 3 4
1 1 0 2
2 6 5
2 1 0
样例输出 #1
3
3
1
提示
Idea：Ynoi，Solution：Ynoi，Code：Ynoi，Data：Ynoi&nzhtl1477
对于 \(100\%\) 的数据，满足
\(2\leq n,q\leq 4\times 10^5\)，\(2\leq l\leq r\leq n\)，\(1\leq x\leq 4\times 10^5\)，\(1\leq u,v\leq n\)。
考虑如何进行求 lca 这个操作。正常的维护肯定是要 LCT 的，但是 LCT 难以支持区间减这种操作。考虑分块。
为什么道题会想到分块呢？因为他是Ynoi由于保证 \(a_i<i\)（操作后更是），所以每个点到根的链都是由 \(\sqrt n\) 个关键链组成的，那么就可以像树剖那样暴力跳，直到跳到关键链顶相同后再暴力跳父亲。复杂度 \(O(\sqrt{n})\)。
那么现在的关键任务就是对每个点维护 \(tp_i\) 表示 \(i\) 所在的关键链的链顶，而一个点的父亲是容易用分块维护的。这样子就可以实现求 lca 的操作。
\(tp_i\) 看起来很难维护，但是由于 \(a_i\) 只减不增，而且当 \(a\) 已经小于这个块最小的点的时候，\(tp_i=i\)，所以 \(tp\) 是均摊会改变 \(O(n\sqrt n)\) 次的。
对于每个块，记录下他还有哪些点满足 \(a_i\) 大于等于块中的最小点，那么每次把这些点暴力改掉就行了。
时间复杂度 \(O(n\sqrt n)\)，空间复杂度 \(O(n)\)
#include<bits/stdc++.h>
using namespace std;
const int B=650,N=4e5+5;
int a[N],ls,n,m,tg[N],tp[N],s[B][B],k[B],g[N],q,op,l,r,x;
int ask(int x)
{
return max(1,g[x]-tg[x/B]);
}
void upd(int u,int l,int r,int x)
{
if(l==u*B&&r==u*B+B-1)
tg[u]=min(n,tg[u]+x);
else
for(int j=l;j<=r;j++)
g[j]=max(g[j]-x,1);
for(int j=1;j<=k[u];j++)
{
if(l<=s[u][j]&&s[u][j]<=r)
{
a[s[u][j]]=max(a[s[u][j]]-x,1);
if(a[s[u][j]]<u*B||a[s[u][j]]==1)
{
if(a[s[u][j]]<u*B)
tp[s[u][j]]=s[u][j];
else
tp[s[u][j]]=1;
for(int i=j;i<k[u];i++)
s[u][i]=s[u][i+1];
--k[u],--j;
}
else
tp[s[u][j]]=tp[a[s[u][j]]];
}
else
tp[s[u][j]]=tp[a[s[u][j]]];
}
}
void upd(int l,int r,int x)
{
if(l/B==r/B)
upd(l/B,l,r,x);
else
{
upd(l/B,l,l/B*B+B-1,x);
for(int i=l/B+1;i<r/B;i++)
upd(i,i*B,i*B+B-1,x);
upd(r/B,r/B*B,r,x);
}
}
int ask(int u,int v)
{
while(tp[u]^tp[v])
{
if(tp[u]<tp[v])
swap(u,v);
u=ask(tp[u]);
}
while(u^v)
{
// if(q==984)
// printf("qzmlovehjh:%d %d\n",u,v);
if(u<v)
swap(u,v);
u=ask(u);
}
return u;
}
int main()
{
// freopen("a.in","r",stdin);
// freopen("b.out","w",stdout);
scanf("%d%d",&n,&q);
tp[1]=1;
for(int i=2;i<=n;i++)
{
scanf("%d",a+i),g[i]=a[i];
if(a[i]<i/B*B)
tp[i]=i;
else if(a[i]==1)
tp[i]=1;
else
tp[i]=tp[a[i]],s[i/B][++k[i/B]]=i;
}
while(q--)
{
scanf("%d",&op);
if(op==1)
scanf("%d%d%d",&l,&r,&x),upd(l^ls,r^ls,x^ls);
else
scanf("%d%d",&l,&r),printf("%d\n",ls=ask(l^ls,r^ls));
}
}