望先生不吝赐教

· · 题解

800 年之前加到主题库里面的 Ynoi。突然意识到哦原来这是个 Global Round 的题目。刚出来的时候挼了好久都没搞出来，看了眼做法没去补……结果今天在赛时突然遇见了，然后就写出来了。当然这是题外话。

这个题显然不可能维护出树的形态，也不好用 \log 一类东西去维护。于是考虑根号算法。

联想到树链剖分求 LCA。在树链剖分求 LCA 的做法中，我们优化时间复杂度的方法是，构造「重链」这样一个概念，优化了在重儿子中往上跳的复杂度。将序列分块，我们需要构造一个方法，使得跳 LCA 的时间复杂度是 O(\sqrt n)。因为只会往前跳，不难想到处理每个点块外的最近祖先，这样我们可以在 O(\sqrt n) 的时间内跳到某一个祖先的块内，并且以 O(\sqrt n) 的时间复杂度在块内暴力找到这个祖先。之后以这样的方式跳 LCA：

现在的话，我们需要维护的东西有一个点块外的最近祖先和其父亲结点。考虑维护方法。

注意到在一个块修改了很多次之后，这个块内的父亲节点和块外最近祖先其实是一个东西。发现这个值最大是这个块的长度，即 O(\sqrt n)。因此我们一个块最多修改 O(\sqrt n) 次，共 O(\sqrt n) 个块。总共的时间复杂度是 O(n \sqrt n)，是完全支持我们去重构的。至于散块我们直接修改重构肯定没有问题。

如果一个块被修改了多次，我们就可以直接打懒标记了。最后查询块外最近祖先和父亲的时候，先判断一下是否存在标记，如果有标记就说明父亲已经到块外去了，直接跳就行。具体可以看代码。

#include<bits/stdc++.h>
using namespace std;
int read()
{
    int x=0;
    char c=getchar();
    while(c<'0' || c>'9')   c=getchar();
    while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0'),c=getchar();
    return x;
}
void write(int x)
{
    if(x>=10)   write(x/10);
    putchar(x%10+'0');
}
const int MAXN=100010;
int n,T,brk,bel[MAXN],L[505],R[505],tag[505],sum[505],fa[MAXN],top[MAXN];
int getAcOut(int x){return sum[bel[x]]>brk?max(1,fa[x]-tag[bel[x]]):top[x];}
int getAcIn(int x){return sum[bel[x]]>brk?max(1,fa[x]-tag[bel[x]]):fa[x];}
void modify(int x){if(sum[bel[x]]<=brk) top[x]=(bel[fa[x]]!=bel[x])?fa[x]:top[fa[x]];}
void modify(int x,int val)
{
    if(sum[x]>brk)  tag[x]=min(tag[x]+val,n);
    else    for(int i=L[x];i<=R[x];++i) fa[i]=max(fa[i]-val,1),modify(i);
}
void modify(int lp,int rp,int val)
{
    int l=bel[lp],r=bel[rp];
    if(l==r)
    {
        for(int i=lp;i<=rp;++i) fa[i]=max(fa[i]-val,1);
        for(int i=lp;i<=R[r];++i)   modify(i);
        return ;
    }
    for(int i=lp;i<=R[l];++i)   fa[i]=max(fa[i]-val,1),modify(i);
    for(int i=L[r];i<=rp;++i)   fa[i]=max(fa[i]-val,1);
    for(int i=L[r];i<=R[r];++i) modify(i);
    for(int i=l+1;i<=r-1;++i)   modify(i,val),++sum[i];
}
int main(){
    n=read(),T=read();
    brk=sqrt(n);
    for(int i=2;i<=n;++i)   fa[i]=read();
    fa[1]=top[1]=1;
    for(int i=1;i<=n;++i)   bel[i]=(i-1)/brk+1;
    for(int i=1;i<=n;++i)
    {
        if(!L[bel[i]])  L[bel[i]]=i;
        R[bel[i]]=i;
    }
    for(int i=2;i<=n;++i)   modify(i);
    while(T-->0)
    {
        int op=read();
        if(op==1)
        {
            int l=read(),r=read(),x=read();
            modify(l,r,x);
        }
        else
        {
            int u=read(),v=read();
            while(u!=v)
            {
                int acu=getAcOut(u),acv=getAcOut(v);
                if(bel[acu]!=bel[acv])
                {
                    if(bel[acu]<bel[acv])   v=acv;
                    else    u=acu;
                }
                else if(acu!=acv)
                {
                    if(acu<acv) v=acv;
                    else    u=acu;
                }
                else
                {
                    if(u<v) v=getAcIn(v);
                    else    u=getAcIn(u);
                }
            }
            write(u),puts("");
        }
    }
    return 0;
}