#P2488. 树套树-简单版

树套树-简单版

2488. 树套树-简单版(线段树套平衡树)

题目描述

请你写出一种数据结构,来维护一个长度为 nn 的序列,其中需要提供以下操作:

  1. 1 pos x,将 pos 位置的数修改为 xx。
  2. 2 l r x,查询整数 xx 在区间 [l,r][l,r] 内的前驱(前驱定义为小于 xx,且最大的数)。

数列中的位置从左到右依次标号为 1∼n1 \sim n。

区间 [l,r][l,r] 表示从位置 ll 到位置 rr 之间(包括两端点)的所有数字。

输入格式

第一行包含两个整数 nn 和 mm。

第二行包含 nn 个整数,表示有序数列。

接下来 mm 行,每行包含一个操作指令,格式如题目所述。

输出格式

对于所有操作 2,每个操作输出一个查询结果,每个结果占一行。

数据范围

1≤n,m≤5×1041 \le n, m \le 5 \times 10^4, 1≤l≤r≤n1 \le l \le r \le n, 1≤pos≤n1 \le pos \le n, 0≤x≤1080 \le x \le 10^8,

有序数列中的数字始终满足在 [0,108][0, 10^8] 范围内,

数据保证所有操作一定合法,所有查询一定有解。

输入样例

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

输出样例

2
1