题意

给定一棵 $n$ 个结点的有根树，结点编号 $1 \sim n$，根的父亲为 $0$。再给定一个长度为 $m$ 的序列 $a$（$1 \le a_i \le n$）。需要处理 $q$ 个操作，操作有两种：

• 1 x l r：从结点 $x$ 出发，依次遍历序列中 $l \sim r$ 的位置。设当前结点为 $u$，当遍历到 $a_i$ 时，如果 $u$ 有至少 $a_i$ 个儿子，则走向 $u$ 的编号第 $a_i$ 小的儿子；否则停留在 $u$ 并结束。如果顺利走完整个区间，则停留在最后走到的结点。输出最终停留的结点编号。
• 2 t k：将 $a_t$ 修改为 $k$。

数据范围

$n, m, q \le 5 \times 10^5$，所有数均为正整数。

---

思路

1. 从结点到序列的映射

题目中“走向编号第 $a_i$ 小的儿子”意味着：每个结点的所有儿子需要按编号从小到大排序，然后第 $1$ 小的、第 $2$ 小的……编号最小的儿子就是它的第一个儿子。于是，从根出发沿着儿子排名走，可以得到一个唯一的“排名序列”，例如 $[r_1, r_2, \dots, r_k]$ 表示第 $1$ 步走 $r_1$ 号儿子，第 $2$ 步走 $r_2$ 号儿子……最终到达某个结点。

反过来，给定一个起始结点 $x$ 和一个排名序列 $[p_1, p_2, \dots, p_k]$，能否走到某个结点 $y$ 呢？当且仅当从 $x$ 开始，每一步都恰好存在对应排名的儿子，且最后走到的 $y$ 唯一确定。我们可以用哈希来刻画这个对应关系。

2. 哈希

定义根结点的哈希值为 $0$。对于任意结点 $u$，假设它的儿子已经按编号排序，并记 $rank(v)$ 为 $v$ 在 $u$ 的儿子列表中的序号（从 $1$ 开始）。那么结点 $v$ 的哈希值定义为：

$$hash(v) = hash(u) \times B + rank(v)$$

其中 $B$ 是一个大于 $n$ 的底数（例如 $10^6+3$）。这样，从根到 $v$ 的路径上的排名序列就完整地编码进了 $hash(v)$ 中。若从某个结点 $x$ 出发，沿着排名序列 $p_1, p_2, \dots, p_k$ 行走，最终到达的结点 $y$ 应当满足：

$$hash(y) = hash(x) \times B^k + \big(p_1 B^{k-1} + p_2 B^{k-2} + \dots + p_k\big)$$

等号右边第二项恰好就是序列 $[p_1, \dots, p_k]$ 看作一个 $B$ 进制数的哈希值。

因此，我们可以：

• 预处理所有结点的哈希值 $hash[u]$ 和深度 $depth[u]$，并用一个哈希表（unordered_map）将 $hash[u]$ 映射到结点编号 $u$。
• 同时预处理 $B$ 的幂 $powB[i]$，用于快速拼接。

3. 线段树维护哈希

序列 $a$ 中的每个元素就是我们要走的排名。为了能快速获得任意子区间 $[l,r]$ 的哈希值，可以用线段树维护：

• 每个结点存储该区间所对应排名序列的哈希值。
• 合并规则：左区间长度为 $len_L$，右区间长度为 $len_R$，则父结点哈希值为$$hash_{parent} = hash_{left} \times B^{len_R} + hash_{right}$$这符合字符串哈希的拼接性质。

线段树支持单点修改（操作 2）和区间哈希查询（虽未直接用到区间查询，但我们需要将 $[l,r]$ 分解成线段树上的若干完整区间，以便分段处理）。

4. 查询

对于操作 1 x l r，我们将区间 $[l,r]$ 在线段树上分解为若干个连续的完整区间（个数为 $O(\log m)$），然后依次处理每个区间。

假设当前所在结点为 cur，当前处理的区间为 $[L,R]$（线段树结点 $p$ 对应），区间长度为 $len$，哈希值为 $seg\_hash$。计算目标哈希：

$$target = hash[cur] \times B^{len} + seg\_hash$$

在哈希表中查找是否存在结点 $v$ 使得 $hash[v] = target$ 且 $depth[v] = depth[cur] + len$。如果存在，说明这个区间可以完整走完，我们将 cur 更新为 $v$，继续处理下一个区间。

如果不存在，说明在这个区间内的某一步失败了。我们需要在这个区间内二分查找第一个失败的位置，返回最终停下的结点。具体做法（递归函数 find_fail(p, L, R, cur)）：

• 如果 $L = R$（区间长度为 1），计算单步目标：$target = hash[cur] \times B + a[L]$。若存在结点 $v$ 满足条件，则走这一步，返回 $v$；否则停留在 $cur$。
• 否则，取中点 $mid$，先检查左半区间能否完整走完：
  • 左半区间长度 $len_L = mid-L+1$，哈希值 $left\_hash$ 可从线段树左孩子获得。
  • 左半目标 $target_L = hash[cur] \times B^{len_L} + left\_hash$。
  • 如果存在对应结点 $v_L$ 且深度符合，说明左半区间可以完整走完，则令 $cur = v_L$，递归处理右半区间（p*2+1, mid+1, R, cur）。
  • 否则递归处理左半区间（p*2, L, mid, cur）。

这个递归过程类似于在线段树上二分，时间复杂度 $O(\log m)$。

由于我们将原区间分成了 $O(\log m)$ 个完整区间，但最多只会进入一次 find_fail（因为一旦失败就返回，不再处理后面的区间），因此单次查询的复杂度为 $O(\log^2 m)$。

5. 修改

操作 2 t k 直接修改线段树叶子结点的值，并向上更新父结点哈希值。复杂度 $O(\log m)$。

复杂度分析

• 预处理：$O(n + m)$。
• 建树：$O(m)$。
• 单次查询：$O(\log^2 m)$。
• 单次修改：$O(\log m)$。
• 总复杂度：$O((n+m+q)\log^2 m)$，在 $5\times 10^5$ 的数据范围下可以接受（实际常数较小）。

---

总结

本题巧妙地将树上的路径行走转化为哈希拼接问题，利用线段树维护区间哈希，实现了快速查询和修改。分段处理与二分查找的思想是解决此类“中途可能失败”的区间查询的常用技巧。

代码

#include<bits/stdc++.h>
using namespace std;

typedef unsigned long long ULL;
const int N = 5e5 + 10;
const ULL BASE = 1e6 + 3;

int n, m, q;
vector<int> child[N];
int f[N], depth[N];
ULL hash_val[N], pow_base[N];
unordered_map<ULL, int> mp;   //mp[哈希值] = 5；
int a[N];

struct segtree{
    ULL hash;
} tree[N << 2];

void build(int p, int l, int r)
{
    if(l == r) {
        tree[p].hash = a[l];
        return;
    }

    int mid = l + r >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    int right_len = r - mid;
    tree[p].hash = tree[p << 1].hash * pow_base[right_len] + tree[p << 1 | 1].hash;
    
}
void update(int p, int l, int r, int pos, int val)
{
    if(l == r)
    {
        tree[p].hash = val;
        a[l] = val;
        return;
    }
    int mid = l + r >> 1;
    if(pos <= mid) update(p << 1, l, mid, pos, val);
    else update(p << 1 | 1, mid + 1, r, pos, val);
    int right_len = r - mid;
    tree[p].hash = tree[p << 1].hash * pow_base[right_len] + tree[p << 1 | 1].hash;
}

struct SegInfo{
    int p, L, R;
};
vector<SegInfo> segs;

void get_segs(int p, int l, int r, int ql, int qr)
{
    if(ql <= l && r <= qr)
    {
        segs.push_back({p, l, r});
        return ;
    }
    int mid = l + r >> 1;
    if(ql <= mid) get_segs(p << 1, l, mid, ql, qr);
    if(qr > mid) get_segs(p << 1 | 1, mid + 1, r, ql, qr);
}

int find_p(int p, int L, int R, int cur)
{
    if(L == R)
    {
        ULL target = hash_val[cur] * BASE + tree[p].hash;
        auto it = mp.find(target);
        if(it != mp.end() && depth[it->second] == depth[cur] + 1)
        {
            return cur = it->second;
        }
        else return cur;
    }
    int mid = L + R >> 1;
    int left_len = mid - L  + 1;
    ULL left_hash = tree[p << 1].hash;
    ULL target = hash_val[cur] * pow_base[left_len] + left_hash;
    auto it = mp.find(target);
    if(it != mp.end() && depth[it->second] == depth[cur] + left_len)
    {
        int new_cur = it->second;
        return find_p(p << 1 | 1, mid + 1, R, new_cur);
    }
    else 
        return find_p(p << 1, L, mid, cur);
}


int query(int x, int l, int r)
{
    segs.clear();
    get_segs(1, 1, m, l, r); //将查询区间在线段树上拆分成若干个互不相交且连续的完整区间。
    int cur = x;
    for(auto &seg : segs)
    {
        int p = seg.p, L = seg.L, R = seg.R;
        int len = R - L + 1;
        ULL seg_hash = tree[p].hash;
        ULL target = hash_val[cur] * pow_base[len] + seg_hash;
        auto it = mp.find(target);
        if(it != mp.end() && depth[it->second] == depth[cur] + len)
        {
            cur = it->second;
        }
        else 
        {
            return find_p(p, L, R, cur); //在区间[L, R]中找不能到的点。
        }
    }
    return cur;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0); //加速输入

    cin >> n >> m >> q;
    for(int i = 1; i <= n; i++)
        cin >> f[i];
    
    int root = 0;
    for(int i = 1; i <= n; i++)
    {
        if(f[i] == 0) root = i;
        else child[f[i]].push_back(i);
    }

    //每个结点的儿子按编号排序
    for(int i = 1; i <= n; i++)
            sort(child[i].begin(), child[i].end());

    //BFS来计算深度和哈希值
    queue<int> qq;
    depth[root] = 0;
    hash_val[root] = 0;
    mp[0] = root; //哈希值为0的点是root
    qq.push(root);
    while(!qq.empty())
    {
        int u = qq.front(); qq.pop();
        int rk = 1;
        for(int v : child[u])
        {
            depth[v] = depth[u] + 1;
            hash_val[v] = hash_val[u]*BASE + rk;
            mp[hash_val[v]] = v;
            qq.push(v);
            rk ++;
        }
    }

    for(int i = 1; i <= m; i++)
        cin >> a[i];

    //计算BASE的幂
    pow_base[0] = 1;
    for(int i = 1; i <= m; i++)
        pow_base[i] = pow_base[i - 1] * BASE;

    build(1, 1, m);
    while(q --)
    {
        int op;
        cin >> op;
        if(op == 1)
        {
            int x, l, r;
            cin >> x >> l >> r;
            cout << query(x, l, r) << endl;
        }
        else
        {
            int t, k;
            cin >> t >> k;
            update(1, 1, m, t, k);
        }
    }
    return 0;
}