#P6794. [SNOI2020] 水池

[SNOI2020] 水池

题目描述

有一个长条形的水池,可以划分成 nn 格。其中第 ii 格和 i+1i+1 格之间相邻,由一块高度为 hih_i 的可调节挡板隔开。第 11 格左侧和第 nn 格右侧是无限高的池壁。初始时水池中没有水。现在进行 qq 次操作,操作有以下四种:

  • 0 i x h 在第 xx 格灌水直到该格的水面高度不低于 hh(若当前水面高度已经达到 hh 则无事发生);
  • 1 i x 打开第 xx 格底部的排水口直到该格的水流干,再关闭排水口;
  • 2 i x h 将第 xx 格右侧的挡板高度增加到 hh(不改变现有水面,保证挡板高度不会下降);
  • 3 i x 查询第 xx 格的水面高度。

其中,ii 表示这次操作是基于第 ii 次操作之后的情况,i=0i=0 表示基于初始状态。也就是说,这个问题要求对操作可持久化。

输入格式

第一行两个自然数 n,qn,q,表示水池格数和操作次数。
接下来一行 n1n - 1 个正整数 hih_i 表示挡板的初始高度。
接下来 qq 行每行一个正整数表示一次操作。

输出格式

对每个操作 33 输出一行一个整数表示答案。

4 9
1 3 2
0 0 4 2
3 1 1
0 2 4 3
3 3 1
0 4 4 4
3 5 1
2 6 1 4
1 7 4
3 8 1
0
0
4
4

提示

样例说明

对于样例 11

数据规模与约定

对于所有数据,1n,q2×105,0hi1091\le n,q\le 2\times 10^5, 0\le h_i\le 10^9

  • 对于 10%10\% 的数据,n500n \le 500
  • 对于另外 20%20\%,没有操作 11,且 ii00 开始连续增长(不需要可持久化);
  • 对于另外 20%20\%,没有操作 11
  • 对于另外 20%20\%,且 ii00 开始连续增长(不需要可持久化);
  • 对于余下 30%30\% 的数据,无特殊限制。