Description
给定一个含有n个数的序列a[1],a[2],a[3]……a[n]，程序必须回答这样的询问：对于给定的i,j,k，在a[i],a[i+1],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1)，并且，你可以改变一些a[i]的值，改变后，程序还能针对改变后的a继续回答上面的问题。你需要编一个这样的程序，从输入文件中读入序列a，然后读入一系列的指令，包括询问指令和修改指令。对于每一个询问指令，你必须输出正确的回答。第一行有两个正整数n(1≤n≤10000)，m(1≤m≤10000)。分别表示序列的长度和指令的个数。第二行有n个数，表示a[1],a[2]……a[n]，这些数都小于10^9。接下来的m行描述每条指令，每行的格式是下面两种格式中的一种。Q
i j k 或者 C i tQ i j k （i,j,k是数字，1≤i≤j≤n, 1≤k≤j-i+1）表示询问指令，询问a[i]，a[i+1]……a[j]中第k小的数。C i t (1≤i≤n，0≤t≤10^9)表示把a[i]改变成为t。
i j k 或者 C i tQ i j k （i,j,k是数字，1≤i≤j≤n, 1≤k≤j-i+1）表示询问指令，询问a[i]，a[i+1]……a[j]中第k小的数。C i t (1≤i≤n，0≤t≤10^9)表示把a[i]改变成为t。
Input
对于每一次询问，你都需要输出他的答案，每一个输出占单独的一行。
Output
Sample Input
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
Sample Output
3
6
6
HINT
20%的数据中，m,n≤100;
40%的数据中，m,n≤1000;
100%的数据中，m,n≤10000。
无限仰慕WJMZBMR。
看了他的集训队论文给了我很大的启发。
预祝WJMZBMR大神进入国家队。
这个是支持修改的区间第k大问题。
首先想不修改的区间第k大问题，由于权值线段树可以进行四则运算，所以可以由两棵线段树相减得到一颗描述区间的线段树，然后log查询。
这个本质是前缀和。
前缀和修改为O(n)，查询为O(1)，修改实在是非常慢，而且对空间要求非常大，所以我们希望将修改和查询的耗时进行平衡。
说到可修改的前缀和，容易想到树状数组，所以按修改树状数组的方式修改logn棵线段树，查询的时候访问logn棵线段树在权值线段树上查询，修改时间复杂度O(log^2)，所需空间复杂度O(log^2)，查询与其相同。
虽然学到了新算法，但是破灭了一个梦想觉得很不高兴。
你看啊，函数式编程不就像世界线吗……我可以从一个世界线不断前行，也可以用电话微波炉回到过去进入别的世界线……但是这样无法体现世界线的收敛，也就是即使发送dmail让世界线走到分叉也能回到注定的世界线，可是树状数组解决了这个问题，但是完全不能体现啊……………………………………………………超~不~爽。
program bzoj1901;
var
len,all,tot,n,m,i,j,k:longint;
s,root:array [0..10001] of longint;
new,dl:array [0..20001] of longint;
que:array [0..10001] of record
t:char;
i,j,k:longint;
end;
left,right,sum:array [0..4000001] of longint;
procedure swap (var a,b:longint);inline;
begin
if a=b then exit;
b:=a xor b;
a:=a xor b;
b:=a xor b;
end;
procedure qsort (s,e:longint);
var
i,j,k:longint;
begin
if s>=e then exit;
i:=s;
j:=e;
k:=dl[(s+e) div 2];
while i<=j do
begin
while dl[i]<k do inc(i);
while dl[j]>k do dec(j);
if i>j then break;
swap(dl[i],dl[j]);
inc(i);
dec(j);
end;
qsort(s,j);
qsort(i,e);
end;
function convert (now:longint):longint;inline;
var
mid,s,e:longint;
begin
s:=1;
e:=all;
while s<>e do
begin
mid:=(s+e) div 2;
if new[mid]<now then s:=mid+1
else e:=mid;
end;
exit(s);
end;
procedure build (s,e,now:longint);
var
mid:longint;
begin
if s=e then exit;
mid:=(s+e) div 2;
inc(tot);
left[now]:=tot;
build(s,mid,tot);
inc(tot);
right[now]:=tot;
build(mid+1,e,tot);
end;
function lowbit (x:longint):longint;inline;
begin
exit(x xor (x and (x-1)));
end;
procedure insert (p,w,x:longint);inline;
var
l,r,last,now,mid:longint;
begin
while x<=n do
begin
l:=1;
r:=all;
last:=root[x];
inc(tot);
root[x]:=tot;
now:=tot;
repeat
sum[now]:=sum[last]+p;
if l=r then break;
mid:=(l+r) div 2;
inc(tot);
if w<=mid then
begin
left[now]:=tot;
right[now]:=right[last];
now:=tot;
last:=left[last];
r:=mid;
end
else
begin
left[now]:=left[last];
right[now]:=tot;
now:=tot;
last:=right[last];
l:=mid+1;
end;
until false;
x:=x+lowbit(x);
end;
end;
function find (i,j,k:longint):longint;
var
o,x,now,l,r,mid:longint;
begin
len:=0;
dec(i);
while i>0 do
begin
inc(len);
dl[len]:=-root[i];
i:=i-lowbit(i);
end;
while j>0 do
begin
inc(len);
dl[len]:=root[j];
j:=j-lowbit(j);
end;
l:=1;
r:=all;
while l<>r do
begin
mid:=(l+r) div 2;
now:=0;
for i:=1 to len do
begin
o:=dl[i] div abs(dl[i]);
x:=abs(dl[i]);
now:=now+o*sum[left[x]];
end;
if now<k then
begin
k:=k-now;
for i:=1 to len do
begin
o:=dl[i] div abs(dl[i]);
x:=abs(dl[i]);
dl[i]:=right[x]*o;
end;
l:=mid+1;
end
else
begin
for i:=1 to len do
begin
o:=dl[i] div abs(dl[i]);
x:=abs(dl[i]);
dl[i]:=left[x]*o;
end;
r:=mid;
end;
end;
exit(l);
end;
begin
readln(n,m);
for i:=1 to n do
begin
read(s[i]);
dl[i]:=s[i];
end;
readln;
tot:=n;
for i:=1 to m do
begin
read(que[i].t);
if que[i].t='Q' then
read(que[i].i,que[i].j,que[i].k)
else
begin
read(que[i].i,que[i].j);
inc(tot);
dl[tot]:=que[i].j;
end;
readln;
end;
qsort(1,tot);
i:=1;
while i<=tot do
begin
inc(all);
new[all]:=dl[i];
while dl[i]=new[all] do inc(i);
end;
for i:=1 to n do
s[i]:=convert(s[i]);
for i:=1 to m do
if que[i].t='C' then
que[i].j:=convert(que[i].j);
tot:=0;
build(1,all,0);
for i:=1 to n do
insert(1,s[i],i);
for i:=1 to m do
if que[i].t='Q' then
writeln(new[find(que[i].i,que[i].j,que[i].k)])
else
begin
insert(-1,s[que[i].i],que[i].i);
insert(1,que[i].j,que[i].i);
s[que[i].i]:=que[i].j
end;
end.