我们就建一颗线段树，线段树的每一个节点都是一颗平衡树，对于每个询问来说，我们就二分答案，

查询每个二分到的mid在这个区间里的rank，然后就行了

/**************************************************************    Problem: 1901    User: BLADEVIL    Language: Pascal    Result: Accepted    Time:3220 ms    Memory:6592 kb****************************************************************/ //By BLADEVILtype    rec                     =record        left, right, root   :longint;    end; var    n, m                    :longint;    a                       :array[0..10010] of longint;    t                       :array[0..40010] of rec;    bt                      :array[0..300000] of longint;    b_size, b_left, b_right :array[0..300000] of longint;    b_key                   :array[0..300000] of longint;    tot                     :longint;     function min(a,b:longint):longint;begin    if a>b then min:=b else min:=a;end; function max(a,b:longint):longint;begin    if a>b then max:=a else max:=b;end;     procedure rotate_right(var t:longint);var    k                       :longint;begin    k:=b_left[t];    b_left[t]:=b_right[k];    b_right[k]:=t;    b_size[k]:=b_size[t];    b_size[t]:=b_size[b_right[t]]+b_size[b_left[t]]+1;    t:=k;end; procedure rotate_left(var t:longint);var    k                       :longint;begin    k:=b_right[t];    b_right[t]:=b_left[k];    b_left[k]:=t;    b_size[k]:=b_size[t];    b_size[t]:=b_size[b_right[t]]+b_size[b_left[t]]+1;    t:=k;end;     procedure maintain(var t:longint; flag:boolean);begin    if not flag then    begin        if b_size[b_left[b_left[t]]]>b_size[b_right[t]] then            rotate_right(b_left[t]) else        if b_size[b_right[b_left[t]]]>b_size[b_right[t]] then        begin            rotate_left(b_left[t]);            rotate_right(t);        end else exit;    end else    begin        if b_size[b_right[b_right[t]]]>b_size[b_left[t]] then            rotate_left(b_right[t]) else        if b_size[b_left[b_right[t]]]>b_size[b_left[t]] then        begin            rotate_right(b_right[t]);            rotate_left(t);        end else exit;    end;    maintain(b_left[t],false);    maintain(b_right[t],true);    maintain(t,true);    maintain(t,false);end;     procedure insert(var t:longint; v:longint);begin    if t=0 then    begin        inc(tot);        t:=tot;        b_left[t]:=0;        b_right[t]:=0;        b_size[t]:=1;        b_key[t]:=v;    end else    begin        inc(b_size[t]);        if v>=b_key[t] then            insert(b_right[t],v) else            insert(b_left[t],v);        maintain(t,v>=b_key[t]);    end;end;     function delete(var t:longint; v:longint):longint;begin    dec(b_size[t]);    if (b_key[t]=v)         or (b_right[t]=0) and (v>b_key[t])         or (b_left[t]=0) and (v
     
      mid then change(x*2+1,y,z) else change(x*2,y,z);end; function ask(x,l,r,k:longint):longint;var    mid                     :longint;begin    ask:=0;    if (t[x].left=l) and (t[x].right=r) then    begin        ask:=rank(t[x].root,k);        exit;    end;    with t[x] do mid:=(left+right) div 2;    if mid
      
       =r then ask:=ask(x*2,l,r,k) else    ask:=ask(x*2,l,mid,k)+ask(x*2+1,mid+1,r,k);end; function succ(var t:longint;v:longint):longint;begin    if t=0 then exit(-1);    if b_key[t]
       
        v then pred:=pred(b_left[t],v) else    begin        pred:=pred(b_right[t],v);        if pred=-1 then pred:=b_key[t];     end;end; function ask_succ(x,l,r,y:longint):longint;var    mid                     :longint;begin    if (t[x].left=l) and (t[x].right=r) then    begin        ask_succ:=succ(t[x].root,y);        if ask_succ=-1 then ask_succ:=maxlongint;        exit;    end;    with t[x] do mid:=(left+right) div 2;    if l>mid then ask_succ:=ask_succ(x*2+1,l,r,y) else    if r<=mid then ask_succ:=ask_succ(x*2,l,r,y) else    ask_succ:=min(ask_succ(x*2,l,mid,y),ask_succ(x*2+1,mid+1,r,y));end; function ask_pred(x,l,r,y:longint):longint;var    mid                     :longint;begin    if (t[x].left=l) and (t[x].right=r) then    begin        ask_pred:=pred(t[x].root,y);        exit;    end;    with t[x] do mid:=(left+right) div 2;    if l>mid then ask_pred:=ask_pred(x*2+1,l,r,y) else    if r<=mid then ask_pred:=ask_pred(x*2,l,r,y) else    ask_pred:=max(ask_pred(x*2,l,mid,y),ask_pred(x*2+1,mid+1,r,y));end; procedure query(x,y,k:longint);var    l, r, mid               :longint;    ans                     :longint;    xx                      :longint;begin    l:=1; r:=1000000000;    while l<=r do    begin        mid:=(l+r) div 2;        xx:=ask(1,x,y,mid);        if xx>=k-1 then        begin            ans:=mid;            r:=mid-1;        end else l:=mid+1;    end;    if ask(1,x,y,ans)<>k-1 then        xx:=ask_pred(1,x,y,ans-1) else        xx:=ask_succ(1,x,y,ans);    writeln(xx);end; procedure init;var    i                       :longint;begin    read(n,m);    for i:=1 to n do read(a[i]);    readln;    build(1,1,n);end; procedure main;var    i                       :longint;    ch                      :char;    l, r, x                 :longint;     begin    for i:=1 to m do    begin        read(ch);        if ch='Q' then        begin            readln(l,r,x);            query(l,r,x);        end else        begin            readln(l,x);            change(1,l,x);            a[l]:=x;        end;    end;end; begin    init;    main;end.