关于pbds的hash

rt，这个题 我用cchash和umap都能过但是用gphash #5直接满了几百倍，求大佬解答。

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define ll unsigned long long
using namespace std;
using namespace __gnu_pbds;
namespace IO
{
    char buff[1<<21],*p1=buff,*p2=buff;
    char getch(){return p1==p2&&(p2=((p1=buff)+fread(buff,1,1<<21,stdin)),p1==p2)?EOF:*p1++;}
    template<typename T>void read(T &x){char ch=getch();int fl=1;x=0;while(ch>'9'||ch<'0'){if(ch=='-')fl=-1;ch=getch();}while(ch<='9'&&ch>='0'){x=x*10+ch-48;ch=getch();}x*=fl;}
    template<typename T>void read_s(T &x){char ch=getch();while(ch<'a'||ch>'z')ch=getch();while(ch>='a'&&ch<='z'){x+=ch;ch=getch();}}
    template<typename T,typename ...Args>void read(T &x,Args& ...args){read(x);read(args...);}
    char obuf[1<<21],*p3=obuf;
    void putch(char ch) {if(p3-obuf<(1<<21))*p3++=ch;else fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=ch;}
    char ch[100];
    template<typename T>void write(T x) {if(!x)return putch('0');if(x<0)putch('-'),x*=-1;int top=0;while(x)ch[++top]=x%10+48,x/=10;while(top)putch(ch[top]),top--;}
    template<typename T,typename ...Args>void write(T x,Args ...args) {write(x);write(args...);}
    void put(string s){for(int i=0;i<s.size();i++)putch(s[i]);}
    void flush(){fwrite(obuf,p3-obuf,1,stdout);}
}
using namespace IO;
int n,m,q;
vector<int>e[500005];
ll Pow[500005];
ll a[500005];
int f[500005];
ll h[500005];
const ll base=(2e6+3);
cc_hash_table<ll,int>mp;
//unordered_map<ll,int>mp;
void dfs(int u)
{
    mp[h[u]]=u;
    for(int i=0;i<e[u].size();i++)
    {
        int v=e[u][i];
        h[v]=h[u]*base+i+1;
        dfs(v);
    }
}
namespace Nene
{
    struct segt
    {
        int len;
        ll val;
        inline segt operator+(const segt &a)const
        {
            segt res;
            res.len=len+a.len;
            res.val=val*Pow[a.len]+a.val;
            return res;
        }
    }t[500005<<2];
    #define ls (root<<1)
    #define rs (root<<1|1)
    #define mid (l+r>>1)
    void insert(int x,ll v,int root=1,int l=1,int r=m)
    {
        if(l==r) return t[root].val=v,t[root].len=1,void();
        if(x<=mid) insert(x,v,ls,l,mid);
        else insert(x,v,rs,mid+1,r);
        t[root]=t[ls]+t[rs];
    }
    vector<int>rt(100),tl(100),tr(100);
    void get(int x,int y,int root=1,int l=1,int r=m)
    {
        if(l>=x&&r<=y) return rt.push_back(root),tl.push_back(l),tr.push_back(r),void();
        if(x<=mid) get(x,y,ls,l,mid);
        if(y>mid) get(x,y,rs,mid+1,r);
    }
    const ll f1=18446744073709551615ull;
    ll find(ll now,int root,int l,int r)
    {
        if(mp.find(now)==mp.end()) return f1;
        if(l==r) return mp.find(now*base+t[root].val)==mp.end()?now:now*base+t[root].val;
        if(mp.find(now*Pow[t[ls].len]+t[ls].val)==mp.end()) return find(now,ls,l,mid);
        return find(now*Pow[t[ls].len]+t[ls].val,rs,mid+1,r);
    }
    inline ll query(int p,int x,int y)
    {
        rt.clear();tl.clear();tr.clear();
        ll now=h[p];
        get(x,y);
        for(int i=0;i<rt.size();i++)
        {
            if(mp.find(now*Pow[t[rt[i]].len]+t[rt[i]].val)==mp.end()) 
            {
                ll tmp=find(now,rt[i],tl[i],tr[i]);
                return tmp==f1?p:mp[tmp];
            }
            now=now*Pow[t[rt[i]].len]+t[rt[i]].val;
        }
        return mp[now];
    }
    #undef mid
}using namespace Nene;
int main()
{
//  freopen("P5537_5.in","r",stdin);
//  freopen(".out","w",stdout);
    read(n,m,q);
    int rt;
    for(int i=1;i<=n;i++) 
    {
        read(f[i]);
        if(!f[i]) rt=i;
        else e[f[i]].push_back(i);
    }
    for(int i=1;i<=n;i++) sort(e[i].begin(),e[i].end());
    Pow[0]=1;
    for(int i=1;i<=500000;i++) Pow[i]=Pow[i-1]*base;
    dfs(rt);
    for(int i=1;i<=m;i++) read(a[i]),insert(i,a[i]);
    while(q--)
    {
        int op,x,ql,qr;read(op,x,ql);
        if(op==1) read(qr),write(query(x,ql,qr)),putch('\n');
        else insert(x,ql),a[x]=ql;
    }
    flush();
    return 0;
}