Mon3tr
为了复活凯尔希,Mon3tr 给了你一棵由编号为 1,2,…,n 的点构成的有根树,根节点编号为 1。每个点有两个点权 ai 和 idi,点 i 的父亲为 fai。
记 di 为点 i 到树根的唯一简单路径上的点数,所以根节点的 d1=1。
现在有 q 次修改与询问:
-
修改操作给定 x,v,将 idx 修改为 v。
-
询问操作给定 x,y,z。对于每个点 i,令 l 为点 i,x 的最近公共祖先。在满足
idi−dl≤y≤idi,idi+al≤z
的所有点中,求 idi+al 的最大值。如果不存在符合条件的点,答案为 0。
输入格式
第一行包含四个整数 c,n,q,o,分别为子任务编号、树的点数、操作数量及是否强制在线。特别地,c=0 表示样例。
第二行包含 n 个整数 id1,id2,…,idn。
第三行包含 n 个整数 a1,a2,…,an。
第四行包含 n−1 个整数 fa2,fa3,…,fan,保证 fai<i。
接下来 q 行,每行表示一个操作。设 lastans 为上一次询问的答案,若尚未进行询问,则 lastans=0。修改操作不影响 lastans。
-
1 x' v':先解密
x=((x′−1+o⋅lastans)modn)+1,
v=((v′−1+o⋅lastans)modn)+1,
然后将 idx 修改为 v。
-
2 x' y' z':先解密
x=((x′−1+o⋅lastans)modn)+1,
y=((y′+(n−1)+o⋅lastans)mod(2n−1))−(n−1),
z=((z′−1+o⋅lastans)mod(2n−1))+1,
然后进行询问。
输出格式
对于每次询问,输出一行一个整数表示答案。
样例 1
0 16 20 1
15 8 2 11 13 14 3 15 13 6 16 6 4 1 8 16
2 9 16 10 3 13 11 2 6 14 15 8 16 6 16 13
1 1 3 3 4 3 6 8 8 3 6 1 12 6 3
2 16 -9 9
2 14 7 19
2 9 7 28
2 12 13 1
2 10 2 18
2 11 14 20
2 9 -7 23
2 7 4 25
1 12 11
2 3 -8 23
2 14 6 11
2 14 -2 31
1 6 15
2 15 13 8
1 2 6
2 5 -15 26
1 15 4
2 7 -14 7
1 10 12
2 14 0 23
0
10
0
0
18
4
0
22
0
0
7
0
0
0
18
其他样例
下载完整样例附件。样例 2 至 6 分别满足子任务 1、2、3、4、6 的约束条件。
数据范围
- 2≤n≤105,q≤2×105,o∈{0,1};
- 1≤idi,ai≤n,1≤fai<i;
- 1≤x,x′,v,v′≤n;
- 1−n≤y,y′≤n−1;
- 1≤z,z′≤2n−1。
| 子任务 |
分值 |
n≤ |
q≤ |
特殊性质 |
| 1 |
5 |
1000 |
无 |
| 2 |
15 |
105 |
2×105 |
无修改,fai=i−1 |
| 3 |
10 |
o=0,所有询问的 x=1 |
| 4 |
20 |
无修改,所有 ai=1 |
| 5 |
无修改 |
| 6 |
30 |
无 |
每个子任务采用捆绑测试。