自动搬运

查看原文

来自洛谷，原作者为

	Hanghang 2025冲冲冲

搬运于2025-08-24 22:11:47，当前版本为作者最后更新于2023-10-30 19:55:29，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

妙妙题。介绍一下单 $\log$ 做法。

首先我们观察到树形态不变，那么我们可以快速求出根到每个点的序列值，通过差分也就可以知道任意祖孙点对中间的序列值。

我们需要快速查询一个序列值是否出现过，自然也就想到哈希。

哈希也是支持快速合并的，也就满足序列上的单点修改性质。

那么现在也就变成了查询最大的 $r$，满足 $L \le r \le R$ 满足根到 $x$ 的哈希值加上 $[L,r]$ 的哈希值出现过。

显然 $r$ 是满足单调性的，就可以线段树二分 (不懂为什么其他题解的线段树二分为啥是俩 $\log$ )，现在对单 $\log$ 做法进行讲解。

首先从左往右找到所有满足 $L\le l \le r \le R$ 的 $\log$ 个极大子区间，再记录一个 $cur$ 变量记录当前哈希值。

如果 $cur$ 加上当前区间 $[l,r]$ 的哈希值，如果这个值出现过就加入，然后向后循环。

否则，那么答案 $r$ 一定在 $[l,r]$ 中，直接向下递归，具体就是：

加入左子树的哈希值，如果出现过就加入，递归右子树，否则递归左子树。

那么两部分的复杂度是分开的，都是单 $\log$，那么总复杂度也就是单 $\log$。

注意到这里的哈希值很大，使用 map 会被卡常，建议使用 pb_ds 或者手写哈希表，不会 pb_ds 的右转 如何优雅地使用 pb_ds。

跑得飞快，目前是 rk3，默认 $n,m,q$ 同阶的话，总复杂度为 $O(n \log n)$。

还有不懂的可以看代码，任何问题欢迎与我交流：

#include<bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
const int N=5e5+3;
int n,m,q,rt,a[N],fa[N];
vector<int>ve[N]; 
ull bas=2e6+3,pri=229,cur=0,pw[N],sx[N],tr[N*4];
cc_hash_table<ull,int>mp;
int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return x*f;
}
void write(int X)
{
	if(X<0){putchar('-');X=~(X-1);}int s[20],o=0;
	while(X){s[++o]=X%10;X/=10;}
	if(!o)s[++o]=0;while(o)putchar(s[o--]+'0');
	putchar('\n');
}
void Dfs(int x,int fa)
{
	mp[sx[x]]=x;
	for(int i=0,y;i<(ll)ve[x].size();i++)if((y=ve[x][i])!=fa)
	    sx[y]=sx[x]*bas+i+1+pri,Dfs(y,x);
}
#define ls (p<<1)
#define rs (p<<1|1)
#define mi ((l+r)>>1)
void Up(int p,int len){tr[p]=tr[ls]*pw[len]+tr[rs];}
void Build(int p,int l,int r)
{
	if(l==r){tr[p]=a[l]+pri;return;}
	Build(ls,l,mi);Build(rs,mi+1,r);Up(p,r-mi); 
}
void Upd(int k,int p,int l,int r,int d)
{
	if(l==r){tr[p]=d+pri;return;}
	k<=mi?Upd(k,ls,l,mi,d):Upd(k,rs,mi+1,r,d);Up(p,r-mi);
}
int Ans(int p,int l,int r)
{
	if(l==r)return l;
	ull x=cur*pw[mi-l+1]+tr[ls];
	if(mp.find(x)==mp.end())return Ans(ls,l,mi);
	cur=x;return Ans(rs,mi+1,r);
}
int Ask(int L,int R,int p,int l,int r,int &o)
{
	if(L<=l&&r<=R)
	{
		ull x=cur*pw[r-l+1]+tr[p];
		if(mp.find(x)==mp.end()){o=1;return Ans(p,l,r);}
		cur=x;return 0;
	}
	if(L>mi)return Ask(L,R,rs,mi+1,r,o);
	if(R<=mi)return Ask(L,R,ls,l,mi,o);
	int res=Ask(L,R,ls,l,mi,o);
	return o?res:Ask(L,R,rs,mi+1,r,o); 
}
int main()
{
	n=read();m=read();q=read();pw[0]=1;
	for(int i=1;i<N;i++)pw[i]=pw[i-1]*bas;
	for(int i=1;i<=n;i++)
	{
	    fa[i]=read();
		if(!fa[i])rt=i;
		else ve[fa[i]].push_back(i);
	}
	for(int i=1;i<=m;i++)a[i]=read();
	for(int i=1;i<=n;i++)sort(ve[i].begin(),ve[i].end());
	Dfs(rt,0);Build(1,1,m);
	while(q--)
	{
		int op,x,l,r;op=read();
		if(op==2){l=read();x=read();Upd(l,1,1,m,x);continue;}
		x=read();l=read();r=read();cur=sx[x];
		int fl=0;Ask(l,r,1,1,m,fl);write(mp[cur]);
	}
}