#P7235. [2023省队模拟]水

    ID: 7069 传统题 2000ms 256MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600省选/NOI-可持久化线段树标记永久化线段树上二分历史版本查询离散化

[2023省队模拟]水

题目描述

一个长条形水池分成 nn 格。第 ii 格和第 i+1i+1 格之间有一块可调节高度的挡板,初始高度为 hih_i。第 11 格左侧和第 nn 格右侧是无限高的池壁。初始时水池中没有水。

共有 qq 次操作,每次操作以第 ii 次操作完成后的状态为基础。i=0i=0 表示初始状态。操作分为四种:

  • 0 i x h:在第 xx 格灌水,直到该格的水面高度不低于 hh。如果已经不低于 hh,则不做任何操作。
  • 1 i x:打开第 xx 格底部的排水口,直到该格的水流干,再关闭排水口。
  • 2 i x h:将第 xx 格右侧的挡板高度增加到 hh,不改变现有水面。保证挡板高度不会下降。
  • 3 i x:查询第 xx 格的水面高度。

输入格式

第一行两个自然数 n,qn,q,表示水池格数和操作数。

第二行 n−1n-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

数据范围与约定

对于所有数据,1≤n,q≤2×1051\le n,q\le2\times10^5,0≤hi≤1090\le h_i\le10^9。

  • 对于 10%10\% 的数据,n≤500n\le500。
  • 对于另外 20%20\% 的数据,没有类型为 11 的操作,且 ii 从 00 开始连续递增。
  • 对于另外 20%20\% 的数据,没有类型为 11 的操作。
  • 对于另外 20%20\% 的数据,ii 从 00 开始连续递增。
  • 对于其余 30%30\% 的数据,无特殊限制。