[Ynoi2007] rfplca
题目描述
给定一棵大小为 $n$ 的 $1$ 为根节点的树,树用如下方式给出:输入 $a_2,a_3,\dots,a_n$,保证 $1\leq a_i<i$,将 $a_i$ 与 $i$ 连边形成一棵树。
接下来有 $m$ 次操作,操作有两种:
- `1 l r x` 令 $a_i=\max(a_i-x,1)(l\leq i\leq r)$。
- `2 u v` 查询在当前的 $a$ 数组构成的树上 $u,v$ 的 LCA。
输入输出格式
输入格式
第一行包含两个数 $n$,$m$。
之后一行 $n-1$ 个数,表示 $a_2,...,a_n$。
之后 $m$ 行,每行三个或四个数,表示一次操作。
**本题强制在线,所有输入的 $l,r,x,u,v$ 均需要异或 $lastans$,其定义为上一次询问操作得到的答案,若之前没有询问操作,则为 $0$。**
输出格式
对于每个 $2$ 操作,输出一行一个数表示答案。
输入输出样例
输入样例 #1
6 4
1 2 3 3 4
2 3 4
1 1 0 2
2 6 5
2 1 0
输出样例 #1
3
3
1
说明
Idea:Ynoi,Solution:Ynoi,Code:Ynoi,Data:Ynoi&nzhtl1477
对于 $100\%$ 的数据,满足
$2\leq n,q\leq 4\times 10^5$,$2\leq l\leq r\leq n$,$1\leq x\leq 4\times 10^5$,$1\leq u,v\leq n$。