{"trustable":false,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\t\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n\t MathJax.Hub.Config({\n\t extensions: [\"tex2jax.js\"],\n\t jax: [\"input/TeX\", \"output/SVG\"],\n\t tex2jax: {\n\t inlineMath: [ [\u0027$\u0027,\u0027$\u0027], [\"\\\\(\",\"\\\\)\"] ],\n\t displayMath: [ [\u0027$$\u0027,\u0027$$\u0027], [\"\\\\[\",\"\\\\]\"] ],\n\t processEscapes: true\n\t },\n\t });\n\t\u003c/script\u003e\n\t\u003cscript type\u003d\"text/javascript\"\n\t src\u003d\"https://cdn.staticfile.org/mathjax/2.7.0/MathJax.js\"\u003e\n\t\u003c/script\u003e\n \n \u003cp\u003eThe Company Dynamic Rankings has developed a new kind of computer that is no longer satisfied with the query like to simply find the k-th smallest number of the given N numbers. They have developed a more powerful system such that for N numbers a[1], a[2], ..., a[N], you can ask it like: what is the k-th smallest number of a[i], a[i+1], ..., a[j]? (For some i\u0026lt;\u003dj, 0\u0026lt;k\u0026lt;\u003dj+1-i that you have given to it). More powerful, you can even change the value of some a[i], and continue to query, all the same.\u003cbr\u003e \u003cbr\u003e Your task is to write a program for this computer, which\u003cbr\u003e \u003cbr\u003e - Reads N numbers from the input (1 \u0026lt;\u003d N \u0026lt;\u003d 50,000)\u003cbr\u003e \u003cbr\u003e - Processes M instructions of the input (1 \u0026lt;\u003d M \u0026lt;\u003d 10,000). These instructions include querying the k-th smallest number of a[i], a[i+1], ..., a[j] and change some a[i] to t.\u003c/p\u003e \n \u003cp\u003e\u003cbr\u003e \n给定一个含有n个数的序列a[1],a[2],a[3]……a[n],程序必须回答这样的询问:\u003c/br\u003e\n对于给定的i,j,k,在a[i],a[i+1],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1)\u003c/br\u003e\n并且,你可以改变一些a[i]的值,改变后,程序还能针对改变后的a继续回答上面的问题。\n"}},{"title":"Input","value":{"format":"HTML","content":"\u003c/b\u003e\u003cbr\u003e \u003cbr\u003e The first line of the input is a single number X (0 \u0026lt; X \u0026lt;\u003d 4), the number of the test cases of the input. Then X blocks each represent a single test case.\u003cbr\u003e \u003cbr\u003e The first line of each block contains two integers N and M, representing N numbers and M instruction. It is followed by N lines. The (i+1)-th line represents the number a[i]. Then M lines that is in the following format\u003cbr\u003e \u003cbr\u003e Q i j k or\u003cbr\u003e C i t\u003cbr\u003e \u003cbr\u003e It represents to query the k-th number of a[i], a[i+1], ..., a[j] and change some a[i] to t, respectively. It is guaranteed that at any time of the operation. Any number a[i] is a non-negative integer that is less than 1,000,000,000.\u003cbr\u003e \u003cbr\u003e There\u0027re NO breakline between two continuous test cases.\u003c/p\u003e \n \u003cp\u003e\u003cbr\u003e\n第一个数表示数据组数。\n 第一行有两个正整数n(1≤n≤10000),m(1≤m≤10000)。分别表示序列的长度和指令的个数。\u003c/br\u003e第二行有n个数,表示a[1],a[2]……a[n],这些数都小于10^9。\u003c/br\u003e\n接下来的m行描述每条指令,每行的格式是下面两种格式中的一种。 Q i j k 或者 C i t \u003c/br\u003e\nQ i j k (i,j,k是数字,1≤i≤j≤n, 1≤k≤j-i+1)表示询问指令,询问a[i],a[i+1]……a[j]中第k小的数。\u003c/br\u003eC i t (1≤i≤n,0≤t≤10^9)表示把a[i]改变成为t。"}},{"title":"Output","value":{"format":"HTML","content":"\u003c/b\u003e\u003cbr\u003e \u003cbr\u003e For each querying operation, output one integer to represent the result. (i.e. the k-th smallest number of a[i], a[i+1],..., a[j])\u003cbr\u003e \u003cbr\u003e There\u0027re NO breakline between two continuous test cases.\u003c/p\u003e \n \u003cp\u003e\u003cbr\u003e \n对于每一次询问,你都需要输出他的答案,每一个输出占单独的一行。"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003c/b\u003e\u003cbr\u003e \u003cbr\u003e 2\u003cbr\u003e 5 3\u003cbr\u003e 3 2 1 4 7\u003cbr\u003e Q 1 4 3\u003cbr\u003e C 2 6\u003cbr\u003e Q 2 5 3\u003cbr\u003e 5 3\u003cbr\u003e 3 2 1 4 7\u003cbr\u003e Q 1 4 3\u003cbr\u003e C 2 6\u003cbr\u003e Q 2 5 3\u003c/p\u003e \n \u003cp\u003e\u003cbr\u003e \u003cb"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003c/b\u003e\u003cbr\u003e \u003cbr\u003e 3\u003cbr\u003e 6\u003cbr\u003e 3\u003cbr\u003e 6\u003c/p\u003e \n \u003cp\u003e\u003cbr\u003e \u003ci\u003e (adviser)\u003c/i\u003e\u003cbr\u003e \u003cb\u003eSite:\u003c/b\u003e \u003ca href\u003d\"http://zhuzeyuan.hp.infoseek.co.jp/index.files/our_contest_20040619.htm\"\u003e\u003ci\u003ehttp://zhuzeyuan.hp.infoseek.co.jp/index.files/our_contest_20040619.htm\u003cbr\u003e \u003c/i\u003e\u003c/a\u003e\u003c/p\u003e \n "}}]}