#P7446. [Ynoi2007] rfplca

[Ynoi2007] rfplca

题目描述

给定一棵大小为 nn11 为根节点的树,树用如下方式给出:输入 a2,a3,,ana_2,a_3,\dots,a_n,保证 1ai<i1\leq a_i<i,将 aia_iii 连边形成一棵树。

接下来有 mm 次操作,操作有两种:

  • 1 l r xai=max(aix,1)(lir)a_i=\max(a_i-x,1)(l\leq i\leq r)
  • 2 u v 查询在当前的 aa 数组构成的树上 u,vu,v 的 LCA。

输入格式

第一行包含两个数 nnmm

之后一行 n1n-1 个数,表示 a2,...,ana_2,...,a_n

之后 mm 行,每行三个或四个数,表示一次操作。

本题强制在线,所有输入的 l,r,x,u,vl,r,x,u,v 均需要异或 lastanslastans,其定义为上一次询问操作得到的答案,若之前没有询问操作,则为 00

输出格式

对于每个 22 操作,输出一行一个数表示答案。

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

3
3
1

提示

Idea:Ynoi,Solution:Ynoi,Code:Ynoi,Data:Ynoi&nzhtl1477

对于 100%100\% 的数据,满足 2n,q4×1052\leq n,q\leq 4\times 10^52lrn2\leq l\leq r\leq n1x4×1051\leq x\leq 4\times 10^51u,vn1\leq u,v\leq n