WA #6

WA #7

$Code:$

#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>
#define ls nw<<1
#define rs ls|1
#define mid (l+r>>1)
using namespace std;
typedef unsigned long long ULL;
const int N=500005;
const ULL B=N+4;
vector<ULL> H[N];
vector<int> e[N],p[N];
int n,a[N],m,q,d[N],mx;
ULL ksm[N],t[N<<2],HS[N];
inline int read()
{
	int s=0;char c=getchar();
	while(!isdigit(c))  c=getchar();
	while(isdigit(c))  s=(s<<3)+(s<<1)+(c^48),c=getchar();
	return s;
}
void write(int x) {if(x>9)write(x/10);putchar(48+x%10);}
void build(int nw,int l,int r)
{
	if(l==r)  {t[nw]=a[l];return;}
	build(ls,l,mid);build(rs,mid+1,r);
	t[nw]=t[ls]*ksm[r-mid]+t[rs];
}
void cg(int nw,int l,int r,int x)
{
	if(l==r)  {t[nw]=a[l];return;}
	x<=mid?cg(ls,l,mid,x):cg(rs,mid+1,r,x);
	t[nw]=t[ls]*ksm[r-mid]+t[rs];
}
ULL qr(int nw,int l,int r,int x,int y)
{
	if(x<=l&&r<=y)  return t[nw];
	if(y<=mid)  return qr(ls,l,mid,x,y);
	if(x>mid)  return qr(rs,mid+1,r,x,y);
	return qr(ls,l,mid,x,y)*ksm[y-mid]+qr(rs,mid+1,r,x,y);
}
void dfs(int x,int f,ULL hsh)
{
	HS[x]=hsh;p[d[x]=d[f]+1].push_back(x);mx=d[x]>mx?d[x]:mx;
	for(int i=0;i<e[x].size();i++)  dfs(e[x][i],x,hsh*B+i+1);
}
bool cmp(int x,int y) {return HS[x]<HS[y];}
int main()
{
	n=read(),m=read(),q=read();ksm[0]=1;d[0]=-1;
	for(int i=1;i<=n;i++)  e[read()].push_back(i),ksm[i]=ksm[i-1]*B;
	for(int i=1;i<=m;i++)  a[i]=read();
	build(1,1,m);dfs(e[0][0],0,0); 
	for(int i=1;i<=mx;i++)
	{
		sort(p[i].begin(),p[i].end(),cmp);
		for(int j=0;j<p[i].size();j++)  H[i].push_back(HS[p[i][j]]);
	}
	while(q--)
	{
		int op=read()-1,x=read(),l=read(),r=op?0:read();
		if(op)  a[x]=l,cg(1,1,m,x);
		else
		{
			for(int i=18,L=1<<i,k;~i;i--,L>>=1)
			{
				if((1<<i)>mx-d[x]||(1<<i)>r-l+1)  continue;
				ULL v=HS[x]*ksm[L]+qr(1,1,m,l,l+L-1);
				k=lower_bound(H[d[x]+L].begin(),H[d[x]+L].end(),v)-H[d[x]+L].begin();
				if(k<H[d[x]+L].size()&&H[d[x]+L][k]==v)  x=p[d[x]+L][k],l+=L;
			}write(x),putchar('\n');
		}
	}return 0;
}

ps:有大佬来帮蒟蒻查一下错吗？