自动搬运

查看原文

来自洛谷，原作者为

	xfrvq **

搬运于2025-08-24 22:29:56，当前版本为作者最后更新于2022-03-24 18:30:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

原题 & 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

这样求 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;
}