2554. 可持久化线段树

【题目描述】

为什么说本题是福利呢？因为这是一道非常直白的可持久化线段树的练习题，目的并不是虐人，而是指导你入门可持久化数据结构。

线段树有个非常经典的应用是处理$ RMQ $问题，即区间最大/最小值询问问题。现在我们把这个问题可持久化一下:

"$Q$ $k$ $l$ $r$" 查询数列在第$ k $个版本时，区间$ [l, r] $上的最大值

"$M$ $k$ $p$ $v$" 把数列在第$ k $个版本时的第$ p $个数修改为$ v $，并产生一个新的数列版本

最开始会给你一个数列，作为第$ 1 $个版本。

每次$ M $操作会导致产生一个新的版本。修改操作可能会很多呢，如果每次都记录一个新的数列，空间和时间上都是令人无法承受的。所以我们需要可持久化数据结构:

对于最开始的版本 1 ，我们直接建立一颗线段树，维护区间最大值。

修改操作呢？我们发现，修改只会涉及从线段树树根到目标点上一条树链上logn个节点而已，其余的节点并不会受到影响。所以对于每次修改操作，我们可以只重建修改涉及的节点即可。就像这样:

需要查询第$ k $个版本的最大值，那就从第$ k $个版本的树根开始，像查询普通的线段树一样查询即可。

要计算好所需空间哦

【输入格式】

第一行两个整数$ N, Q $。$ N $是数列的长度，$ Q $表示询问数

第二行$ N $个整数，是这个数列

之后$ Q$行，每行以 0 或者 1 开头，0 表示查询操$ Q $，$ 1 $表示修改操作$ M $，格式为

"$0$ $k$ $l$ $r$" 查询数列在第$ k $个版本时，区间$ [l, r] $上的最大值 或者

"$1$ $k$ $p$ $v$" 把数列在第$ k $个版本时的第$ p $个数修改为$ v $，并产生一个新的数列版本

【输出格式】

对于每个$ M $询问，输出正确答案

【样例输入】

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

【样例输出】

4
5
4
4

【提示】

序列版本 1 : 1 2 3 4 ,

查询版本 1 的$ [1, 4] $最大值为 4;

修改产生版本 2 : 1 2 5 4 ,

查询版本 2 的$ [1, 3] $最大值为 5;

查询版本 1 的$ [4, 4] $最大值为 4;

查询版本 1 的$ [2, 4] $最大值为 4.

【数据范围】

对于$100\%$的数据，保证有$N ≤ 1×10^4,Q ≤ 1×10^5 $

对于每次询问操作的版本号$ k $保证合法，

区间$ [l, r] $一定满足$ 1 ≤ l ≤ r ≤ N $。

【来源】

神$boy♂$出题人: sxysxy。原题见: http://syzoj.com/problem/247