求区间最大值（线段树？）

（pta: 嘴强王者）在召唤师峡谷中，优秀的召唤师总是喜欢比较自己的战斗力强弱，而青铜召唤师也不甘示弱，他们比较嘴炮的强弱。由于他们的嘴炮水平总是不断变化，难以通过人工进行比较，因此请你帮他们开发一个算法，找出其中的嘴强王者。

第一行两个正整数n,m，表示有n个选手，m次操作（1≤n≤105,1≤m≤5000)。

第二行有n个整数，分别表示第i个选手的初始嘴炮值ai；选手的编号从1到n。

接下来有m行，每行三个正整数x,l,r;

当x=1时，这是一个询问操作，询问区间[l,r]里面嘴炮值最高的召唤师，即嘴强王者；

当x=0时，这是一个更新操作，表示选手l的嘴炮值更新为r。

题目保证在每个查询区间内，嘴强王者是唯一的。

对于每个询问操作，在一行里面输出里面的嘴强王者的编号及其嘴炮值，用用空格分隔，行末没有多余空格。

在这里给出相应的输出。例如：

首先想到的是暴力查找，每次遍历 [l, r] ，找到最大值，但是明显会超时O(nm)。

怎么能快速得到 [l, r] 中的最大值呢？假如数组 v[l][r] 刚好存了 [l, r] 的最大值，那么就可以直接得到，但是又出现一个问题，空间不够。

再想一想，假如我们知道 [l, j] 和 [j + 1, r] ，是不是也可以快速求得区间 [l, r] 最大值为 max([l, j], [j + 1, r]) 。

但是要怎么切分呢，这时候应该想到二分，以题目数据为例：

v[0][j] 记录存入的值。

v[1][1] = max(v[0][1], v[0][2]) ，v[1][3] = max(v[0][3], v[0][4])，v[1][5] = max(v[0][5], v[0][6])（关于越界问题可以开更大的空间或者加个条件判断）

v[2][1] = max(v[1][1], v[1][3]) ，v[2][5] = max(v[1][5], v[1][7])

v[3][1] = max(v[2][1], v[2][5])

能找到规律了吗？v[i][j] = max(v[i - 1][j], v[i - 1][j + pow(2, i - 1)]) 其中: j = 0)

所以我们来构造这个数组：

数组构造完了，接下来是考虑怎么找：

假如我们要找[1, 5] 根据数组提供的数据，可以看出来我们只需要比较[1, 4],[5,5], 即：v[2][4],v[0][5]。

关于怎么得到 v[2][4] 的呢，其中由上面函数build()可看出，v[i][j] 包含了包括j在内的后pow(2, i)个数，所以可以直接通过log2(4 - 1 + 1) 来得到 i。