{"trustable":true,"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":"\u003cp\u003e公司动态排名已经开发出一种新型计算机,不再满足于简单地查询给定N个数字中第k小的数字。他们开发了一种更强大的系统,可以针对N个数字a[1]、a[2]、...、a[N]进行查询:询问a[i]、a[i+1]、...、a[j]中第k小的数字是多少?(对于一些i≤j,0\u003ck≤j+1-i,这些条件是你提供给计算机的)。更强大的是,你甚至可以改变一些a[i]的值,然后继续查询,一切如初。\u003cbr\u003e\n \u003cbr\u003e\n 你的任务是为这台计算机编写一个程序,其中包括:\u003cbr\u003e\n \u003cbr\u003e\n - 从输入中读取N个数字(1 ≤ N ≤ 50,000)\u003cbr\u003e\n \u003cbr\u003e\n - 处理输入中的M个指令(1 ≤ M ≤ 10,000)。这些指令包括查询a[i]、a[i+1]、...、a[j]中第k小的数字以及将某些a[i]更改为t。\u003c/p\u003e\n\u003cp\u003e\u003cbr\u003e\n \u003cb\u003e输入\u003c/b\u003e\u003cbr\u003e\n \u003cbr\u003e\n 输入的第一行是一个数字X(0 \u003c X ≤ 4),表示输入的测试用例数。然后X个块分别代表一个单独的测试用例。\u003cbr\u003e\n \u003cbr\u003e\n 每个块的第一行包含两个整数N和M,表示N个数字和M个指令。接下来是N行。第(i+1)行表示数字a[i]。然后是M行,格式如下:\u003cbr\u003e\n \u003cbr\u003e\n Q i j k 或\u003cbr\u003e\n C i t\u003cbr\u003e\n \u003cbr\u003e\n 它表示查询a[i]、a[i+1]、...、a[j]中第k个数字以及将某些a[i]更改为t。保证在任何操作时,任何数字a[i]都是小于1,000,000,000的非负整数。\u003cbr\u003e\n \u003cbr\u003e\n 两个连续测试用例之间没有换行。\u003c/p\u003e\n\u003cp\u003e\u003cbr\u003e\n \u003cb\u003e输出\u003c/b\u003e\u003cbr\u003e\n \u003cbr\u003e\n 对于每个查询操作,输出一个整数表示结果。(即a[i]、a[i+1]、...、a[j]中第k小的数字)\u003cbr\u003e\n \u003cbr\u003e\n 两个连续测试用例之间没有换行。\u003c/p\u003e\n\u003cp\u003e\u003cbr\u003e\n \u003cb\u003e样例输入\u003c/b\u003e\u003cbr\u003e\n \u003cbr\u003e\n 2\u003cbr\u003e\n 5 3\u003cbr\u003e\n 3 2 1 4 7\u003cbr\u003e\n Q 1 4 3\u003cbr\u003e\n C 2 6\u003cbr\u003e\n Q 2 5 3\u003cbr\u003e\n 5 3\u003cbr\u003e\n 3 2 1 4 7\u003cbr\u003e\n Q 1 4 3\u003cbr\u003e\n C 2 6\u003cbr\u003e\n Q 2 5 3\u003c/p\u003e\n\u003cp\u003e\u003cbr\u003e\n \u003cb\u003e样例输出\u003c/b\u003e\u003cbr\u003e\n \u003cbr\u003e\n 3\u003cbr\u003e\n 6\u003cbr\u003e\n 3\u003cbr\u003e\n 6\u003c/p\u003e\n\u003cp\u003e\u003cbr\u003e\n\u003ci\u003e\n (顾问)\u003c/i\u003e\u003cbr\u003e\n \u003cb\u003e网站:\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\n \u003c/i\u003e\u003c/a\u003e\u003c/p\u003e"}}]}