P5537 【XR-3】系统设计

· · 题解

妙妙题。介绍一下单 \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]);
    }
}