[题解] CF1491H Yuezheng Ling and Dynamic Tree

Alex_Eon · 2023-07-04 14:19:41 · 题解

Change log

• 2023.7.10 将横向排列的表格改为竖向排版。
• 2023.7.10 修复标点误用问题。

\color{red}博客内食用效果更佳（点我）

思路：分块

复杂度：O(n\sqrt n)

题解中涉及到的变量：

主体思路

先将数列分块，记录每个节点的前驱为 to_i（to_1=1），每个节点跳转至第一个不同块节点 nex_i（若 i 节点在第一个块内，则 nex_i=1）。

维护 nex_i 只需要将序列从前往后扫一遍，用前面的节点更新后面的节点。

若改变一个值，只会影响到块内指向它的节点。当整个区间所有的节点都满足 to_i=nex_i（即跳转一次出块），那么修改一个节点便不会影响其他节点。对于一个块来说，减少的总值大于等于块长时，一定可以保证所有节点一次性跳转出块。维护 sub_i 表示第 i 块整块减少的总值，当 sub_i 大于等于块长时无需重构。

考虑修改操作：

• 对于碎块：暴力修改并重构块。
• 对于整块：
  • 当 sub_i<blen（blen 为块长）时，暴力重构。
  • 当 sub_i\ge blen 时，记录 sb_i 表示第 i 个块在无需被重构时被整体减的总值。

考虑查询操作：

• 先将两节点按照 nex_i-sb_{bl_i}（bl_i 为 i 节点所在块的编号）跳转，将编号更大的节点跳转。
• 当两节点的 nex 相同的时候，就按照 to_i-sb_{bl_i} 跳转，直到两节点汇合。

复杂度分析（浅谈）：

块长为 \sqrt n。

• 预处理：O(n)。
• 查询：单次 O(\sqrt n)，总计 O(q\sqrt n)。
• 修改：
  • 碎块：单次 O(\sqrt n)，总计 O(q\sqrt n)。
  • 整块（最劣）：前 \sqrt n 次 O(n)，后来 O(\sqrt n)，总计约 O(n\sqrt n+q\sqrt n)。

综上，整体复杂度可以看作 O(n\sqrt n)。

代码实现需要注意的地方：

• 维护 sb_i 时需注意保证其小于 n，防止溢出。
• 调用、更新 to_i,nex_i 时要保证两者不小于 1。

参考代码：

参考代码中变量名与题解中均一致，详见注释，感觉可读性还不错。

#define LL long long
#define UN unsigned
#include<bits/stdc++.h>
using namespace std;
//--------------------//
const int N=1e5+1;

int n,q;
int to[N],nex[N];
int blen,bcnt,bl[N];
int sub[N],sb[N];
struct BL{int l,r;}d[N];

void updata(int id)//暴力重构整个块
{
    for(int i=d[id].l;i<=d[id].r;i++)
        if(to[i]==1||bl[i]!=bl[to[i]])//若 to[i] 已经出块便记录
            nex[i]=to[i];
        else
            nex[i]=nex[to[i]];//否则继承
    return;
}

void init()//初始化
{
    blen=sqrt(n);
    for(int i=1;i<=n;i++)
        bl[i]=(bl[i-1]*blen+1==i)?++bcnt:bcnt;//处理每个节点所在块
    for(int i=1;i<=bcnt;i++)
        d[i].l=(i-1)*blen+1,d[i].r=min(n,i*blen),updata(i);//处理块左右节点，以及初始构造
    return;
}

int query(int x,int y)
{
    while(nex[x]!=nex[y])
    {
        if(y>x)
            swap(x,y);//跳转编号大的
        x=max(1,nex[x]-sb[bl[x]]);//保证不越界
    } 
    if(x==y)
        return x;
    while(x!=y)
    {
        if(y>x)
            swap(x,y);
        x=max(1,to[x]-sb[bl[x]]);
    } 
    return x;
}

void change(int l,int r,int x)
{
    int now1=bl[l],now2=bl[r];
    if(now1==now2)
    {
        for(int i=l;i<=r;i++)
            to[i]=max(1,to[i]-x);
        updata(now1);
        return;
    }

    for(int i=l;i<=d[now1].r;i++)//碎块
        to[i]=max(1,to[i]-x);
    updata(now1);
    for(int i=r;i>=d[now2].l;i--)
        to[i]=max(1,to[i]-x);
    updata(now2);
    for(int i=now1+1;i<now2;i++)//整块
    {
        if(sub[i]<blen)//需要暴力重构
        {
            sub[i]+=x;
            for(int j=d[i].l;j<=d[i].r;j++)
                to[j]=max(1,to[j]-x);
            updata(i);
            continue;
        }
        if(sb[i]+x<N)//更新整块加，并保证不越界
            sb[i]+=x;
        else
            sb[i]=N;
    }
    return;
}
//--------------------//
int main()
{
    scanf("%d%d",&n,&q);
    to[1]=1;
    for(int i=2;i<=n;i++)
        scanf("%d",&to[i]);
    int last=0;
    init();
    for(int op,l,r,x,i=1;i<=q;i++)
    {
        scanf("%d%d%d",&op,&l,&r);
        if(op==2)
            last=query(l,r),printf("%d\n",last);
        else
            scanf("%d",&x),change(l,r,x);
    }
    return 0;
}