#P5537. 【XR-3】系统设计

    ID: 4801 远端评测题 2500ms 250MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>字符串线段树二分树状数组O2优化哈希,HASH

【XR-3】系统设计

题目描述

小 X 需要你设计一个系统。

这个系统首先需要输入一棵 nn 个点的有根树和一个长度为 mm 的序列 aa,接下来需要实现 qq 个操作。

操作分两种:

  1. 1 x l r 表示设定起点为有根树的节点 xx,接下来依次遍历 lrl \sim r。当遍历到 ii 时,从当前节点走向它的编号第 aia_i 小的儿子。如果某一时刻当前节点的儿子个数小于 aia_i,或者已经遍历完 lrl \sim r,则在这个点停住,并输出这个点的编号,同时停止遍历。
  2. 2 t k 表示将序列中第 tt 个数 ata_t 修改为 kk

输入格式

第一行 33 个正整数 n,m,qn,m,q,分别表示树的点数、序列的长度和操作个数。

第二行 nn 个整数 f1nf_{1 \dots n},其中 fif_i 表示点 ii 在树中的父亲节点编号,特别地,设根节点为 rtrt,则 frt=0f_{rt} = 0

第三行 mm 个正整数 a1ma_{1 \dots m},表示序列 aa

接下来 qq 行,每行描述一个操作。

数据范围:

  • 1n,m,q5×1051 \le n,m,q \le 5 \times 10 ^ 5
  • 1ain1 \le a_i \le n
  • 对于操作 11,保证 1xn1 \le x \le n1lrm1 \le l \le r \le m
  • 对于操作 22,保证 1tm1 \le t \le m1kn1 \le k \le n

输出格式

对于每个操作 11,一行一个正整数,表示答案。

6 6 10
0 1 2 2 1 5
1 2 2 1 2 1
1 1 1 3
1 5 2 6
1 6 5 6
1 2 3 5
1 2 4 4
2 2 1
1 1 1 6
1 1 2 4
2 1 2
1 1 1 5

4
5
6
4
3
3
4
6

提示

本题读入、输出量较大,请使用读入、输出优化

【样例说明】

第一个操作为 1 1 1 3,即 1241 \rightarrow 2 \rightarrow 4,因此答案为 44

第九个操作后,序列变为 2 1 2 1 2 1

第十个操作为 1 1 1 5,即 1561 \rightarrow 5 \rightarrow 6,因此答案为 66