#P18809. [2027年国家集训队互测]Mon3tr

[2027年国家集训队互测]Mon3tr

Mon3tr

为了复活凯尔希,Mon3tr 给了你一棵由编号为 1,2,…,n1,2,\ldots,n 的点构成的有根树,根节点编号为 11。每个点有两个点权 aia_i 和 idiid_i,点 ii 的父亲为 faifa_i。

记 did_i 为点 ii 到树根的唯一简单路径上的点数,所以根节点的 d1=1d_1=1。

现在有 qq 次修改与询问:

  • 修改操作给定 x,vx,v,将 idxid_x 修改为 vv。

  • 询问操作给定 x,y,zx,y,z。对于每个点 ii,令 ll 为点 i,xi,x 的最近公共祖先。在满足

    idi−dl≤y≤idi,idi+al≤zid_i-d_l\le y\le id_i,\qquad id_i+a_l\le z

    的所有点中,求 idi+alid_i+a_l 的最大值。如果不存在符合条件的点,答案为 00。

输入格式

第一行包含四个整数 c,n,q,oc,n,q,o,分别为子任务编号、树的点数、操作数量及是否强制在线。特别地,c=0c=0 表示样例。

第二行包含 nn 个整数 id1,id2,…,idnid_1,id_2,\ldots,id_n。

第三行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

第四行包含 n−1n-1 个整数 fa2,fa3,…,fanfa_2,fa_3,\ldots,fa_n,保证 fai<ifa_i<i。

接下来 qq 行,每行表示一个操作。设 lastanslastans 为上一次询问的答案,若尚未进行询问,则 lastans=0lastans=0。修改操作不影响 lastanslastans。

  • 1 x' v':先解密

    x=((x′−1+o⋅lastans) mod n)+1,x=((x'-1+o\cdot lastans)\bmod n)+1, v=((v′−1+o⋅lastans) mod n)+1,v=((v'-1+o\cdot lastans)\bmod n)+1,

    然后将 idxid_x 修改为 vv。

  • 2 x' y' z':先解密

    x=((x′−1+o⋅lastans) mod n)+1,x=((x'-1+o\cdot lastans)\bmod n)+1, y=((y′+(n−1)+o⋅lastans) mod (2n−1))−(n−1),y=((y'+(n-1)+o\cdot lastans)\bmod(2n-1))-(n-1), z=((z′−1+o⋅lastans) mod (2n−1))+1,z=((z'-1+o\cdot lastans)\bmod(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≤1052\le n\le10^5,q≤2×105q\le2\times10^5,o∈{0,1}o\in\{0,1\};
  • 1≤idi,ai≤n1\le id_i,a_i\le n,1≤fai<i1\le fa_i<i;
  • 1≤x,x′,v,v′≤n1\le x,x',v,v'\le n;
  • 1−n≤y,y′≤n−11-n\le y,y'\le n-1;
  • 1≤z,z′≤2n−11\le z,z'\le2n-1。
子任务 分值 n≤n\le q≤q\le 特殊性质
1 5 10001000 无
2 15 10510^5 2×1052\times10^5 无修改,fai=i−1fa_i=i-1
3 10 o=0o=0,所有询问的 x=1x=1
4 20 无修改,所有 ai=1a_i=1
5 无修改
6 30 无

每个子任务采用捆绑测试。