P7446 [Ynoi2007] rfplca

· · 题解

原题 & CF 双倍经验, 16th

题意

给定一棵以 1 为根的树 fa_2,\cdots,fa_n 与 m 个操作，这里满足 fa_i\lt i

操作 1: 给定区间 [l,r]，将这个区间的 fa_i\gets \max(fa_i-x,1)
操作 2: 求两点最近公共祖先

题解

建议先写 P3203 [HNOI2010]弹飞绵羊 的分块做法。这里可参考的一点是：维护 top_x 代表 x 一直跳，跳出当前块后到达的第一个点。

虽然这个题看起来是树上的重构与 LCA，但是和 树剖/LCT 等树上算法没有关系。

考虑分块，对于每个位置维护 pa_i 代表这个点离开块的第一个祖先，fa_i 代表这个点的父亲。

那么转化求 LCA 的过程：定义 小跳 为 i\gets fa_i 在块内跳父亲，大跳 为 i\gets pa_i 在块间跳祖先。于是求一次 LCA 就等价于：对于两点不停做以下操作

这样求 LCA，比较容易和修改兼容，仔细观察还会发现和树剖类似（pa_i 其实就是树剖的重链链头父亲），但是树剖因为重链性质所以是 \log n 的，而这里是分块跳法，平衡大跳小跳，复杂度是 \sqrt n。

对于修改，小块重构，但是注意：修改 l\sim r 应该重构 l\sim 块 r 右端点。大块？发现好像只能重构？？

好，其实不是这样的。注意到因为它给出的树的方法与修改树的方法都比较特别，所以得知 \sqrt n 次整块修改后一个块内每个元素跳 fa 都会出块，此时 pa_i=fa_i，打个标记即完事。

于是我们维护 chg_i 代表块 i 被修改的次数，tag_i 代表目前被修改的标记的总和。如果 chg_i\lt\sqrt n 就暴力重构，否则这时每个元素一定跳父亲后会出块。

代码

这里放一个比较 lj 的实现。

long long 很有必要，，

#include<stdio.h>
#include<math.h>
#include<vector>

namespace IO{ } // by OneZzz6174

using IO::read;
using IO::readc;
using IO::print;
using IO::flush;

#define rint register int

typedef long long ll;

inline int max2(rint a,rint b){ return a>b?a:b; }
inline int min2(rint a,rint b){ return a<b?a:b; }
inline void swap2(rint &a,rint &b){ a^=b^=a^=b; }

#define rep(i,a,b) for(rint i = (a);i <= (b);++i)

const int maxn = 4e5 + 5;
const int sqr = sqrt(maxn) + 5;

int n,m,b,c;
int st[sqr],ed[sqr],bl[maxn];
int pa[maxn],fa[maxn];
ll tag[sqr]; // 这个要开 long long
int chg[maxn];

void init(){ // 预处理分块的 st,ed,bl 数组
    b = sqrt(n); c = (n - 1) / b + 1;
    rep(i,1,c){
        st[i] = (i - 1) * b + 1;
        ed[i] = i == c ? n : i * b;
        rep(j,st[i],ed[i]) bl[j] = i;
    }
}

#define C(i) (chg[i] <= b) // 这一块再修改是否需要重构
#define Pa(x) (C(bl[x]) ? pa[x] : max2(1,fa[x] - tag[bl[x]]))
#define Fa(x) (C(bl[x]) ? fa[x] : max2(1,fa[x] - tag[bl[x]]))
// pa,fa 数组只有在 chg[bl[i]]<=b 的时候才有用，所以这里写一个在任何时候都有用的 pa,fa 询问

void chg1(int i){ // 单独更新 1 个点的 pa 值，这种写法可以的原因是 fa[i]<i
    if(C(bl[i])) pa[i] = bl[i] ^ bl[fa[i]] ? fa[i] : pa[fa[i]];
}

void chg2(int i,int x){ // 修改一个块
    if(!C(i)) return void(tag[i] = min2(tag[i] + x,n)); // 如果不用重构，那么加 tag
    rep(j,st[i],ed[i]) fa[j] = max2(1,fa[j] - x),chg1(j); // 重构
}

void upd0(int l,int r,int x){ // 修改零散块
    rep(i,l,r) fa[i] = max2(1,fa[i] - x); // 修改 l~r
    rep(i,l,ed[bl[r]]) chg1(i); // 要重构的位置是 l~end[bl[r]] !!!!!
    // 原因：前面的修改可能会对这个块后面的位置产生影响
}

void upd(int l,int r,int x){ // 真正的修改函数
    if(bl[l] == bl[r]) return upd0(l,r,x); // 零散块
    upd0(l,ed[bl[l]],x); upd(st[bl[r]],r,x); // 零散块
    rep(i,bl[l] + 1,bl[r] - 1) chg2(i,x),++chg[i]; // 整块暴力重构/打tag
}

int qry(int u,int v){ // 求 LCA
    while(u ^ v){ // u=v 时即为答案
        int pu = Pa(u),pv = Pa(v); // 找到第一个祖先
        if(bl[pu] ^ bl[pv]) bl[pu] < bl[pv] ? v = pv : u = pu;
        // 祖先不在同一块，深度大的必然是编号大的，让它先跳
        else if(pu ^ pv) pu > pv ? u = pu : v = pv;
        // 祖先在同一块，深度大的也必然是编号大的
        else u > v ? u = Fa(u) : v = Fa(v);
        // 编号大的来小跳
    }
    return u;
}

signed main(){
    read(n,m);
    fa[1] = pa[1] = 1; /* this */ init();
    rep(i,2,n) fa[i] = read(),chg1(i);
    int op,l,r,lst = 0;
    while(m--){
        read(op,l,r); l ^= lst,r ^= lst;
        op == 1 ? upd(l,r,read() ^ lst) : print(lst = qry(l,r),'\n');
    }
    return flush(),0;
}