题目大意：
一个长度为n的序列，支持两种操作：
1.输出[A, B]区间第k小的数(从小到大排序后第k个)
2.修改第I个数为W
格式
输入：
第一行两个整数N（1<=N<=50000),M(1<=M<=10000),表示有N个数，M个操作
第二行N个数A(1<=A<=1000000000)
以下M行，每行一个操作
Q i j k（查询中第k小的数）或 C i W(把第I个数改成W）
（N，M 可改为【1，100000】）

输出：
对于每个查询操作，输出每个查询结果。

思路：
求带修改的区间第k值有几种方法。可以分块，可以用线段树套平衡树，也可以用树状数组套主席树。我用的是树状数组套主席树。那么就来浅谈树状数组套主席树吧。
首先，主席树就相当于添加节点的线段树的历史版本。在不带修改的区间第k值中，我们是利用两棵树的前缀信息（T[1][l-1], T[1][r]），来查找区间第k值的。那么，要维护前缀信息，就可以用树状数组。
这里的树状数组，并不是专门开一个数组来记录，也并不是创建N个树状数组，只是利用树状数组的lowbit思想，把各历史版本的线段树联系起来。如图：

如果A[i]表示添加了第i个数之后的线段树（存离散化后的值的大小，这些树的结构一样），那么，根据树状数组的思想，A[1]有的节点，A[2]也有，同时A[4],A[8]...都有，但是，A[3],A[5],A[6]...没有。根据不带修改的区间第k值，要求区间【L，R】的第k值，要用两个指针，分指T【1】【L-1】 & T【1】【R】，通过比较两节点左子树权值之差与k，决定是到左孩子还是右孩子。这里与那里差不多，只不过，要求的T【1】【L-1】的左子树权值，需要把与这个节点相关（通过lowbit联系）的节点线段树中的对应节点的左权值都加起来。求T【1】【R】的是一样的。再通过比较两差与k，便可以知道是到左孩子，还是右孩子了。
为了方便，可以先开两个数组，储存当前考察的一系列节点的地址，就可以直接算左权值之和。算完了之后，再遍历数组中的每个点，更新为这个点的左孩子或右孩子（具体要看左权值之差与k的大小比较情况）。要注意的是，如果当前点没有左儿子（或右儿子），那么就要给这个点赋值，存一个每个域都为0的点，这样就可以避免运行错误和重复计算某个节点。
修改的话，若要修改第i个数，那么就先修改树S【i】，再向上lowbit，把跟它有关的树都要修改。具体的修改方法，先把这个点从树中删掉，再把修改后的值加入树中。删除的时候要注意，如果是用动态指针，删完回溯的时候，把空节点删掉，节省空间。
大概就这样了～～
还有一个问题，就是，在最初建树的时候，是根据每个数的离散值来存入线段树的，在把修改后的数加入树的时候，因为你不知到它的离散值是多少，所以不能知道这个数应该存在哪里。因此，在离散之前，先把所有命令全部读完，把要修改的值存在原序列数组的后面（就接在第N个数之后），做个标记，然后一起排序，一起离散。建树的时候只要根据标记来判断该数是否为原序列中的数。但是，这样的话，如果多次对同一个数进行修改，那么，就会出现这个问题，在修改中的删除操作中，找不到这个点（因为它之前已经被删掉了！）。因此，在每次修改后，要把这个数的离散值改为修改后的数的离散值，这样，就跟这个数没有任何关系了。（一开始没发现这个问题，就调了很久。。。）

代码（在下的程序风格很丑，特别长，有废话，不够简洁，还请多多包涵！）：
program p1665;
type
wv2=^wv1;   //线段树；
wv1=record
lw,w,rw,data:longint;  //为了节省空间，线段的左右端点就用递归传值，不单独开域存了；
lc,rc:wv2;
end;
wv3=record
i,j,k:longint;
end;
wv4=record
data:longint;
bb:boolean;  //标记，true为是原序列中的元素；
end;
var
n,m,i,j,k,l,o,xx,
wei,//原序列元素数量与修改数量之和；
delta,topl,topr,suml,sumr,num:longint;
tree,tl,tr:array[0..60000] of wv2;
a:array[1..200000] of wv4;//序列；
b,c:array[1..200000] of longint;//c存离散值；
ttt:array[1..10000] of wv3;//每个命令；
ch1:char;
j1:wv2;//上文所说的“每个域都为0的点”；


function lowbit(x:longint):longint;
begin
exit(x and (x xor (x-1)));
end;

procedure quick(q1,q2:longint);
var i,j,t:longint;x:wv4;
begin
i:=q1;j:=q2;x:=a[i];
while i<j do
begin
while (i<j) and (x.data<=a[j].data) do j:=j-1;
if i<j then begin a[i]:=a[j];t:=b[i];b[i]:=b[j];b[j]:=t;i:=i+1;end;
while (i<j) and (a[i].data<=x.data) do i:=i+1;
if i<j then begin a[j]:=a[i];t:=b[i];b[i]:=b[j];b[j]:=t;j:=j-1;end;
a[i]:=x;
end;
if i>q1+1 then quick(q1,i-1);
if j<q2-1  then quick(j+1,q2);
end;

procedure init;
begin
for i:=1 to n do begin read(a[i].data);b[i]:=i;a[i].bb:=true;end;readln;wei:=n;
for i:=1 to m do
begin
read(ch1);
if ch1='Q' then readln(ttt[i].i,ttt[i].j,ttt[i].k) else 
begin
readln(ttt[i].i,ttt[i].j);ttt[i].k:=-maxlongint;
inc(wei);a[wei].data:=ttt[i].j;b[wei]:=wei;
a[wei].bb:=false;//设标记；
end;
end;
quick(1,wei);c[b[1]]:=1;
for i:=2 to wei do//离散；
if a[i].data<>a[i-1].data then c[b[i]]:=i
else c[b[i]]:=c[b[i-1]];
end;

procedure build(j:wv2;l,r,x:longint);
var mid:longint;j1:wv2;
begin
if l=r then
begin
inc(j^.w);j^.data:=x;exit;
end;
mid:=(l+r)>>1;
if x<=mid then
begin
if j^.lc=nil then 
begin 
new(j^.lc);j1:=j^.lc;
j1^.lw:=0;j1^.rw:=0;j1^.w:=0;j1^.lc:=nil;j1^.rc:=nil;
end;
inc(j^.lw);
build(j^.lc,l,mid,x);
end else
begin
if j^.rc=nil then
begin
new(j^.rc);j1:=j^.rc;
j1^.lw:=0;j1^.rw:=0;j1^.w:=0;j1^.lc:=nil;j1^.rc:=nil;
end;
inc(j^.rw);
build(j^.rc,mid+1,r,x);
end;
end;

procedure bbuuiilldd;//建树；
begin
for i:=0 to n do tree[i]:=nil;
j:=0;new(tree[j]);tree[j]^.w:=0;tree[j]^.lw:=0;tree[j]^.rw:=0;tree[j]^.lc:=nil;tree[j]^.rc:=nil;
for i:=1 to n do
begin
j:=i;
while j<=n do
begin
if tree[j]=nil then
begin 
new(tree[j]);tree[j]^.w:=0;tree[j]^.lw:=0;tree[j]^.rw:=0;tree[j]^.lc:=nil;tree[j]^.rc:=nil;
end;
   build(tree[j],1,wei,c[i]);
delta:=lowbit(j);
j:=j+delta;
   end;
end;
end;

procedure delayyy(j:wv2;o,l,r:longint);  //删除节点；
var
mid,yoki:longint;
begin
if l=r then
begin
j^.data:=0;dec(j^.w);
exit;
end;
mid:=(l+r)>>1;
if o<=mid then
begin
yoki:=1;dec(j^.lw);
delayyy(j^.lc,o,l,mid);
end else
begin
yoki:=2;dec(j^.rw);
delayyy(j^.rc,o,mid+1,r);
end;
if j^.lw=0 then j^.lc:=nil;
if j^.rw=0 then j^.rc:=nil;
end;

procedure prominences;
var
l,r,mid,
oy:longint;//差；
begin
num:=n;
for xx:=1 to m do
if ttt[xx].k<>-maxlongint then
begin
l:=1;r:=wei;
topl:=0;topr:=0;k:=ttt[xx].k;
i:=ttt[xx].i-1;
while i>0 do
begin
topl:=topl+1;tl[topl]:=tree[i];
i:=i-lowbit(i);
end;
i:=ttt[xx].j;
while i>0 do//找相关的节点；
begin
topr:=topr+1;tr[topr]:=tree[i];
i:=i-lowbit(i);
end;
while l<>r do
begin
mid:=(l+r)>>1;
suml:=0;sumr:=0;
for i:=1 to topl do suml:=suml+tl[i]^.lw; //求左权值之和；
for i:=1 to topr do sumr:=sumr+tr[i]^.lw;
oy:=sumr-suml;
if oy>=k then
begin
r:=mid;
for i:=1 to topl do if tl[i]^.lc<>nil then tl[i]:=tl[i]^.lc else tl[i]:=j1;
for i:=1 to topr do if tr[i]^.lc<>nil then tr[i]:=tr[i]^.lc else tr[i]:=j1;
end else
begin
l:=mid+1;k:=k-oy;
for i:=1 to topl do if tl[i]^.rc<>nil then tl[i]:=tl[i]^.rc else tl[i]:=j1;
for i:=1 to topr do if tr[i]^.rc<>nil then tr[i]:=tr[i]^.rc else tr[i]:=j1;
end;
end;
writeln(a[l].data);
end else
begin
i:=ttt[xx].i;k:=ttt[xx].j;
num:=num+1;
while i<=n do
begin
delayyy(tree[i],c[ttt[xx].i],1,wei);
build(tree[i],1,wei,c[num]);
i:=i+lowbit(i);
end;
c[ttt[xx].i]:=c[num];//别忘了这个！
end;
end;
{============================}
begin
readln(n,m);
new(j1);
with j1^ do
begin
lw:=0;rw:=0;w:=0;lc:=nil;rc:=nil;
end;
init;
bbuuiilldd;
prominences;
end.

描述
cjBBteam拥有一个很大的野生动物园。这个动物园坐落在一个狭长的山谷内，这 个区域从南到北被划分成N个区域，每个区域都饲养着一头狮子。这些狮子从北到南编号为1,2,3,…,N。每头狮子都有一个觅食能力值Ai，Ai越小觅食 能力越强。饲养员cmdButtons决定对狮子进行M次投喂，每次投喂都选择一个区间，从中选取觅食能力值第K强的狮子进行投喂。值得注意的 是，cmdButtons不愿意对某些区域进行过多的投喂，他认为这样有悖公平。因此cmdButtons的投喂区间是互不包含的。你的任务就是算出每次 投喂后，食物被哪头狮子吃掉了。格式
输入格式
输入第一行有两个数N和M。此后一行有N个数，从南到北描述狮子的觅食能力值。此后M行，每行描述一次投喂。第t+2的三个数I,J,K表示在第t次投喂中，cmdButtons选择了区间内觅食能力值第K强的狮子进行投喂。

输出格式 
输出有M行，每行一个整数。第i行的整数表示在第i次投喂中吃到食物的狮子的觅食能力值。

思路
一道裸的划分树的题～但是不好打。。
还可以的划分树资料

代码
program p1081;{划分树}const
    emp=100000;
type
    wv1=record
        val,                                                                                //tree[i].val[j] 表示第i层第j个数的值；
                                                //tree[i].num[i] 表示第i层第j个数在当前区间中，它左边（包括它自己）进入左子树的个数；
      num:array[0..emp] of longint;
    end;
var
    tree:array[0..20] of wv1;                                         //划分树，最多不会超过20层；
    s:array[1..emp] of longint;                                    //储存排序后的数组；
    n,m,i,j,k,xx:longint;
procedure quick(q1,q2:longint);                           //快速排序；
var
    i,j,x:longint;
begin
    i:=q1;j:=q2;x:=s[q1];
    while i<j do
        begin
            while (i<j) and (x<=s[j]) do j:=j-1;
            if i<j then
                begin
                    s[i]:=s[j];
                    i:=i+1;
                end;
            while (i<j) and (s[i]<=x) do i:=i+1;
            if i<j then
                begin
                    s[j]:=s[i];
                    j:=j-1;
                end;
            s[i]:=x;
        end;
    if i>q1+1 then quick(q1,i-1);
    if j<q2-1  then quick(j+1,q2);
end;

procedure build(lft,rht,p:longint);                                         //lft，rht 分别为当前层（第p层）所考察的区间左右端点；
var
    mid,                                                                                                    //mid 表示当前区间的中间位置，取标准数为s[mid]；
    isame,                                                   //isame 表示在的当前区间中，和标准数s[mid]相等，并进入左子树的数的个数；
    same,                                                   //same 表示在当前区间中，和标准数s[mid]相等的、已经进入左子树的数的个数；
    ln,                                                                                           //ln 表示下一个要进入左子树的数即将存在下一层的第几个位置；
    rn:longint;                                                                       //rn 表示下一个要进入右子树的数即将存在下一层的第几个位置；
begin
    if lft=rht exit;                                                                                    //查到了叶子，退出；
    mid:=(lft+rht)>>1;                                                                         //找中间位置；
    isame:=mid-lft+1;                                                                       //刚开始，定初值为[lft, mid]个数，即左孩子的元素个数；
    same:=0;
    for i:=lft to rht do                     //把区间中，小于标准数的数从isame中踢掉，剩下的就是和标准数相等的数的个数；
        if tree[p].val[i]<s[mid] then
            isame:=isame-1;
    ln:=lft;rn:=mid+1;
    for i:=lft to rht do
        begin
            if i=lft then
                begin
                    tree[p].num[i]:=0;                                                        //新建左子树；
                end else
                    tree[p].num[i]:=tree[p].num[i-1];
            if tree[p].val[i]<s[mid] then
                begin
                    tree[p].num[i]:=tree[p].num[i]+1;
                    tree[p+1].val[ln]:=tree[p].val[i];
                    ln:=ln+1;
                end else
            if tree[p].val[i]>s[mid] then
                begin
                    tree[p+1].val[rn]:=tree[p].val[i];
                    rn:=rn+1;
                end else
            if tree[p].val[i]=s[mid] then
                begin
                    if same<isame then                                             //一部分与标准数相等的数进左子树，超过一半的就进右子树；
                        begin
                            same:=same+1;
                            tree[p].num[i]:=tree[p].num[i]+1;
                            tree[p+1].val[ln]:=tree[p].val[i];
                            ln:=ln+1;
                        end else
                        begin
                            tree[p+1].val[rn]:=tree[p].val[i];
                            rn:=rn+1;
                        end;ogle AdS
                end;
            end;
        build(lft,mid,p+1);
        build(mid+1,rht,p+1);
end;

procedure scarlet(o:longint);
begin 
    writeln(o)；
end;

procedure prominences(lft,rht,kk,p:longint);
var
    l,                                                                                            //l 记录区间[i,j]中进入左孩子的元素的个数；
    ll,                                                                                           //ll 记录区间[i,j]中进入左孩子的元素的个数；
    r,                                                                                            //r 记录区间[i,j]中进入右孩子的元素的个数；
    rr,                                                                                          //rr 记录区间[lft,i-1]中进入右孩子的元素的个数；
    mid:longint;
begin
    if (lft=rht) then begin scarlet(tree[p].val[lft]);exit;end;                      //定位到叶子，就输出；
    mid:=(lft+rht)>>1;
    if i=lft then                                                                          //单独考虑区间端点重合的情况；
        begin
            l:=tree[p].num[j];
            ll:=0;
        end else
        begin
            l:=tree[p].num[j]-tree[p].num[i-1];
            ll:=tree[p].num[i-1];
        end;
    if l>=kk then                                                                        //要找的数在左子树；
        begin
            i:=lft+ll;
            j:=lft+ll+l-1;
            prominences(lft,mid,kk,p+1);
        end else
        begin                                                                                //要找的数在右子树；
            r:=j-i+1-l;                                             //r --> [i,j]到右孩子
            rr:=i-lft-ll;                                                //rr --> [lft,j-1]到右孩子
            i:=mid+rr+1;
            j:=mid+r+rr;
            prominences(mid+1,rht,kk-l,p+1);
        end;
end;
{=====================================}
begin
    readln(n,m);
    for i:=1 to n do read(s[i]);
    for i:=1 to n do tree[1].val[i]:=s[i];
    quick(1,n);
    build(1,n,1);
    for xx:=1 to m do
        begin
            readln(i,j,k);
            prominences(1,n,k,1);
        end;
end.