求问复杂度是否正确？若正确则怎么卡常可以不T？

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5;
const int M=5e5+5;
const int Mod=1e9+7;
struct edge{
	int to,nex;
}e[N];
int ecnt,h[N],ff[N],has[N],base[M],a[M],nu[N],inv[M];
int n,m,T,i,rt,x,opt,l,r;
struct tree{
	int l,r,ll,rr,ha;
}tr[M<<1];
int tr_cnt;
struct node{
	int x,y;
};
bool cmp(node a,node b){
	return a.x<b.x;
}
void add(int x,int y){
	e[++ecnt]=(edge){y,h[x]};
	h[x]=ecnt;
}
void dfs(int x){
	int t=0;
	for(int i=h[x];i;i=e[i].nex)
		ff[++t]=e[i].to;
	sort(ff+1,ff+1+t);
	for(int i=1;i<=t;i++){
		has[ff[i]]=has[x]*998244353+i;
		has[ff[i]]%=Mod;
	}
	for(int i=h[x];i;i=e[i].nex)
		dfs(e[i].to);
}
void pu(int p){
	int ls=tr[p].ll,rs=tr[p].rr;
	tr[p].ha=tr[ls].ha*base[tr[rs].r-tr[rs].l+1]%Mod+tr[rs].ha;
	tr[p].ha%=Mod;
}
void build(int &p,int l,int r){
	p=++tr_cnt;
	tr[p]=(tree){l,r,0,0,0};
	if(l==1)nu[r]=p;
	if(l==r){
		tr[p].ha=a[l];
		return;
	}
	int mid=l+r>>1;
	build(tr[p].ll,l,mid);
	build(tr[p].rr,mid+1,r);
	pu(p);
}
void cha(int p,int x,int c){
	if(tr[p].l==tr[p].r){
		tr[p].ha=c;
		return;
	}
	int mid=tr[p].l+tr[p].r>>1;
	if(x<=mid)cha(tr[p].ll,x,c);
	else cha(tr[p].rr,x,c);
	pu(p);
}
int ask(int p,int l,int r){
	if(l>r)return 0;
	if(l<=tr[p].l&&tr[p].r<=r)return tr[p].ha;
	int mid=tr[p].l+tr[p].r>>1;
	if(r<=mid)return ask(tr[p].ll,l,r);
	if(l>mid)return ask(tr[p].rr,l,r);
	int ls=ask(tr[p].ll,l,r),rs=ask(tr[p].rr,l,r);
	return (ls*base[tr[tr[p].rr].r-tr[tr[p].rr].l+1]%Mod+rs)%Mod;
}
int sss,bbb,bc;
map<int,int> f;
bool check(int l,int r,int now){
	int s1;
	s1=sss*base[r-l+1]%Mod+(now-bbb*base[r-l+1]%Mod+Mod)%Mod;
	s1%=Mod;
	if(!f[s1]){
		bc=0;
		return 0;
	}
	else{
		bc=f[s1];
		return 1;
	}
}
int ask1(int p,int l,int r,int now){
	if(tr[p].l==tr[p].r){
		check(l,tr[p].l,now);
		return bc;
	}
	int mid=tr[p].l+tr[p].r>>1;
	if(r<=mid){
		now=(now-tr[tr[p].rr].ha+Mod)%Mod;
		now=now*inv[tr[p].r-mid]%Mod;
		return ask1(tr[p].ll,l,r,now);
	}
	if(mid<l)return ask1(tr[p].rr,l,r,now);
	int s1=(now-tr[tr[p].rr].ha+Mod)%Mod;
	s1=s1*inv[tr[p].r-mid]%Mod;
	if(check(l,mid,s1)){
		int ww=ask1(tr[p].rr,l,r,now);
		check(l,mid,s1);
		if(ww)return ww;
		else return bc;
	}
	else{
		now=(now-tr[tr[p].rr].ha+Mod)%Mod;
		now=now*inv[tr[p].r-mid]%Mod;
		return ask1(tr[p].ll,l,r,now);
	}
}
int work(int l,int r,int x){
	sss=has[x];
	bbb=ask(1,1,l-1);
	int lvshi=ask1(1,l,r,tr[1].ha);
	if(!lvshi)return x;
	else return lvshi;
}
int ksm(int x,int k){
	if(k==0)return 1;
	if(k==1)return x%Mod;
	int s1=ksm(x,k/2);
	if(k&1)return s1*s1%Mod*x%Mod;
	else return s1*s1%Mod;
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m>>T;
	for(i=1;i<=n;i++){
		cin>>x;
		if(x==0)rt=i;
		else add(x,i);
	}
	dfs(rt);
	for(i=1;i<=m;i++)cin>>a[i];
	base[0]=1;inv[0]=1;
	inv[1]=ksm(998244353,Mod-2);
	for(i=1;i<=m;i++)base[i]=base[i-1]*998244353%Mod;
	for(i=2;i<=m;i++)
		inv[i]=inv[i-1]*inv[1]%Mod;
	for(i=1;i<=n;i++)
		f[has[i]]=i;
	int pp;
	build(pp,1,m);
	while(T--){
		cin>>opt;
		if(opt==1){
			cin>>x>>l>>r;
			cout<<work(l,r,x)<<'\n';
		}
		else{
			cin>>x>>l;
			cha(1,x,l);
		}
	}
	return 0;
}