题目描述

定义长度为 $m$ 的整数序列 $c_1,c_2,\dots,c_m$ 的「k 伊茶波数」为： ${\rm val}(c)=<br />\left\{\begin{matrix}<br /> 0,&m<k\\<br /> f_{\left \lfloor \tfrac{m}{2} \right \rfloor +1} ,&m\ge k<br />\end{matrix}\right.$ 其中 $f$ 为将 $c$ 升序排列后的序列。 现在给出长为 $n$ 的序列 $a_1,a_2,\dots,a_n$，常数 $k$ 和 $q$ 次操作。定义两种不同的操作类型： $\hspace{23pt}\bullet\,$操作一：令 $a_x=y$； $\hspace{23pt}\bullet\,$操作二：查询 $\max\limits_{l\le L\le R\le r} {\rm val}(a_{[L,R]})$。官方中文

输入格式

第一行输入三个整数 $n,k,q \left(1 \leq n,q \leq 5 \times 10^4;\ 1 \leq k \leq n\right)$，表示序列长度、常数 $k$、操作次数。 第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n \left(1 \leq a_i \leq 5 \times 10^4\right)$，表示初始序列。 此后 $q$ 行，第 $i$ 行先输入一个整数 $o_i \left(1 \leq o_i \leq 2\right)$，表示第 $i$ 次操作的类型，编号同题干，随后在同一行： $\hspace{23pt}\bullet\,$若 $o_i=1$，输入两个整数 $x_i,y_i \left(1 \leq x_i \leq n;\ 1 \leq y_i \leq 5 \times 10^4\right)$，表示第 $i$ 次操作的参数。 $\hspace{23pt}\bullet\,$若 $o_i=2$，输入两个整数 $l_i,r_i \left(1 \leq l_i \leq r_i \leq n\right)$，表示第 $i$ 次查询的区间。官方中文

保证至少有一次操作二。官方中文

输出格式

对于每次操作二，新起一行输出一个整数，表示答案。官方中文