end
            else
                exit;
        end
    else
        begin
            if sbt[p,sbt[p,sbt[p,t].rsb].rsb].s>
                sbt[p,sbt[p,t].lsb].s then
                lr(p,sbt[p,t].rsb)
            else
            if sbt[p,sbt[p,sbt[p,t].rsb].lsb].s>
                sbt[p,sbt[p,t].lsb].s then
                begin
                    rr(p,sbt[p,t].rsb);
                    lr(p,t);
                end
            else
                exit;
        end;
    maintain(p,sbt[p,t].lsb,true);
    maintain(p,sbt[p,t].rsb,false);
    maintain(p,t,true);
    maintain(p,t,false);
end;
////////// sbt---insert;
procedure insert(p:longint;var t,tot:longint;v:longint);
begin
    if t=0 then
        begin
            inc(tot);
            t:=tot;
            sbt[p,t].key:=v;
            sbt[p,t].s:=1;
            sbt[p,t].lsb:=0;
            sbt[p,t].rsb:=0;
            exit;
        end;
    //
    inc(sbt[p,t].s);


    if v<sbt[p,t].key then
        insert(p,sbt[p,t].lsb,tot,v)
    else
        insert(p,sbt[p,t].rsb,tot,v);
    maintain(p,t,v<sbt[p,t].key);
end;
////////////////--sbt insert2;
procedure insert2(p,num:longint;var t:longint;v:longint);
begin
    if t=0 then
        begin
            t:=num;
            sbt[p,t].s:=1;
            sbt[p,t].key:=v;
            sbt[p,t].lsb:=0;
            sbt[p,t].rsb:=0;
            exit;
        end;
    //
    inc(sbt[p,t].s);
    if v<sbt[p,t].key then
        insert2(p,num,sbt[p,t].lsb,v)
    else
        insert2(p,num,sbt[p,t].rsb,v);
    maintain(p,t,v<sbt[p,t].key);
end;
///////////////sbt--delete;
function delete(p:longint;var t:longint;v:longint):longint;
var
    k:longint;
begin
    if t=0 then
        exit(0);
    dec(sbt[p,t].s);
    if (v=sbt[p,t].key)or
        ((v<sbt[p,t].key)and(sbt[p,t].lsb=0))or
        ((v>sbt[p,t].key)and(sbt[p,t].rsb=0)) then
        begin
            delete:=t;
            if (sbt[p,t].lsb=0)or(sbt[p,t].rsb=0) then
                t:=sbt[p,t].lsb+sbt[p,t].rsb
            else
                begin
                    k:=delete(p,sbt[p,t].lsb,v+1);
                    sbt[p,t].key:=sbt[p,k].key;
                    exit(k);


                end;
            exit;
        end
    else
        begin
            if v<sbt[p,t].key then
                delete:=delete(p,sbt[p,t].lsb,v)
            else
                delete:=delete(p,sbt[p,t].rsb,v);
        end;
end;
////////////////---sbt rank;
function rank(p:longint;var t:longint;v:longint):longint;
begin
    if t=0 then
        exit(0);
    if v=sbt[p,t].key then
        flag:=true;
    if v<sbt[p,t].key then
        rank:=rank(p,sbt[p,t].lsb,v)
    else
        rank:=sbt[p,sbt[p,t].lsb].s+1+rank(p,sbt[p,t].rsb,v);
end;
//////////////////--build sbt;
procedure buildsbt(l,r,p:longint;var tot,root:longint);
var
    i:longint;
begin
    for i:=l to r-1 do
        insert(p,root,tot,a[i]);
end;
//////////////////---buildctree;
procedure buildctree(t:longint);
begin
    buildsbt(ctree[t].l,ctree[t].r,ctree[t].d,ctree[t].tot,ctree[t].root);
    if (ctree[t].l+1=ctree[t].r) then
        exit;
    ctree[t].m:=(ctree[t].l+ctree[t].r)shr 1;
    inc(top);
    ctree[t].lc:=top;
    ctree[top].l:=ctree[t].l;
    ctree[top].r:=ctree[t].m;
    ctree[top].d:=ctree[t].d+1;
    ctree[top].root:=0;
    ctree[top].tot:=ctree[t].l-1;
    buildctree(top);
    inc(top);
    ctree[t].rc:=top;
    ctree[top].l:=ctree[t].m;
    ctree[top].r:=ctree[t].r;
    ctree[top].d:=ctree[t].d+1;
    ctree[top].root:=0;
    ctree[top].tot:=ctree[t].m-1;
    buildctree(top);
end;
///////////////////ctree--find


function makequery(l,r,t,v:longint):longint;
var
    res:longint;
begin
    if (l=ctree[t].l)and(ctree[t].r=r) then
        begin
            exit(rank(ctree[t].d,ctree[t].root,v));
        end;
    if r<=ctree[t].m then
        exit(makequery(l,r,ctree[t].lc,v))
    else
    if l>=ctree[t].m then
        exit(makequery(l,r,ctree[t].rc,v))
    else
        begin
        //exit(
        res:=    makequery(l,ctree[t].m,ctree[t].lc,v);
        res:=res+            makequery(ctree[t].m,r,ctree[t].rc,v);
        exit(res);
        end;
end;
procedure change(o,v,t:longint);
var
    tmp:longint;
begin
    if (ctree[t].l<=o)and(o<ctree[t].r) then
        begin
            tmp:=delete(ctree[t].d,ctree[t].root,a[o]);
            insert2(ctree[t].d,tmp,ctree[t].root,v);
        end;
    if (ctree[t].l+1=ctree[t].r) then
        exit;
    if o<ctree[t].m then
        change(o,v,ctree[t].lc)
    else
        change(o,v,ctree[t].rc);
end;
begin
    fillchar(sbt,sizeof(sbt),0);
    fillchar(ctree,sizeof(ctree),0);
    readln(n,mm);
    max:=0;
    for i:=1 to n do
        begin
            read(a[i]);
            if a[i]>max then
                max:=a[i];
        end;
    readln;
    top:=1;
    ctree[1].l:=1;


    ctree[1].r:=n+1;
    ctree[1].d:=1;
    ctree[1].root:=0;
    buildctree(1);
    for ii:=1 to mm do
        begin
            read(ch);
            case ch of
                'Q':
                begin
                    readln(lll,rrr,k);
                    inc(rrr);
                    l:=0;
                    r:=max+1;
                    while l<r do
                        begin
                            flag:=false;
                            mid:=(l+r) shr 1;
                            tt:=makequery(lll,rrr,1,mid);
                            if (tt=k)and(flag) then
                                break;
                            if tt<k then
                                l:=mid+1
                            else


                                r:=mid;
                        end;
                    if l=r then
                        writeln(l)
                    else
                        writeln(mid);
                end;
                'C':
                begin
                    readln(o,v);
                    change(o,v,1);
                    a[o]:=v;
                    if v>max then
                        max:=v;
                end;
            end;
        end;
end.


这是？！

树套树的程序
我在2月7号上午说的DMK写的程序
平衡树是SBT实现的，用Treap貌似也可以

这个我没看呢，形似k-th number
不过划分树和归并树均很强大的…………

神牛级的程序

我的线段SBT在ZOJ2112上SF了……

            else exit
        else
            if tree[tree[tree[p].le].le].s > tree[tree[p].ri].s then
                rightrotateT ( p )
            else if tree[tree[tree[p].le].ri].s > tree[tree[p].ri].s then begin
                leftrotateT ( tree[p].le );
                rightrotateT ( p );
            end
            else exit;
        maintainT ( tree[p].le , false );
        maintainT ( tree[p].ri , true );
        maintainT ( p , true );
        maintainT ( p , false );
    end;   
procedure insertT ( var p : longint; k : longint );
    begin
        if p = 0 then begin
            p := k;
            exit;
        end;
        inc ( tree[p].s );
        if tree[p].v > tree[k].v then
            insertT ( tree[p].le , k )
        else
            insertT ( tree[p].ri , k );
        maintainT ( p , tree[k].v >= tree[p].v );
    end;
function deleteT ( var p : longint; d : longint ): longint;
    begin
        dec ( tree[p].s );
        if (d=tree[p].v) or (d<tree[p].v)and(tree[p].le=0) or (d>tree[p].v)and(tree[p].ri=0) then begin
            deleteT := tree[p].v;
            if (tree[p].le=0) or (tree[p].ri=0) then begin
                stack := p;
                p := tree[p].le + tree[p].ri;
            end
            else
                tree[p].v := deleteT ( tree[p].le , maxlongint );
        end
        else
            if d<tree[p].v then


                deleteT := deleteT ( tree[p].le , d )
            else
                deleteT := deleteT ( tree[p].ri , d );
    end;   
procedure modifyT ( var p : longint; d , v : longint );
    begin
        deleteT ( p , d );
        tree[stack].v := v;
        tree[stack].le := 0;
        tree[stack].ri := 0;
        tree[stack].s := 1;
        insertT ( p , stack );
    end;
   
function findT ( p , v : longint ): longint;
    begin   
        if p = 0 then exit ( 0 );
        if tree[p].v <= v then
            exit ( tree[tree[p].le].s + 1 + findT ( tree[p].ri , v ) );
        exit ( findT ( tree[p].le , v ) );
    end;
       
procedure buildL;
    var
        i : longint;
    begin
        for i := (1 shl(h+1))-1 downto 1 shl h do begin
            line[i].le := i - ( 1 shl h ) + 1;
            line[i].ri := line[i].le;
            line[i].v := 0;
        end;
        for i := (1 shl h)-1 downto 1 do begin
            line[i].le := line[i shl 1].le;
            line[i].ri := line[i shl 1 xor 1].ri;
            line[i].mid := line[i shl 1 xor 1].le;
            line[i].v := 0;
        end; inc ( h );
    end;
   
procedure insertL ( p : longint );
    var
        i , t , d : longint;
    begin
        d := 1;
        for i := 1 to h do begin
            t := newT;
            tree[t].v := data[p];
            insertT ( line[d].v , t );
            if p < line[d].mid then


                d := d shl 1
            else
                d := d shl 1 xor 1;
        end;
    end;
   
procedure modifyL ( p , v : longint );
    var
        i , d : longint;
    begin
        if v = data[p] then exit;
        d := 1;
        for i := 1 to h do begin
            modifyT ( line[d].v , data[p] , v );
            if p < line[d].mid then
                d := d shl 1
            else
                d := d shl 1 xor 1;
        end;
        data[p] := v;
    end;
   
function findL ( p , l , r , v : longint ): longint;
    begin
        if (line[p].le=l) and (line[p].ri=r) then
            exit ( findT ( line[p].v , v ) );
        if r<line[p].mid then
            exit ( findL ( p shl 1 , l , r , v ) );
        if l>=line[p].mid then
            exit ( findL ( p shl 1 xor 1 , l , r , v ) );
        exit ( findL ( p shl 1 , l , line[p].mid xor 1 , v ) + findL ( p shl 1 xor 1 , line[p].mid , r , v ) );
    end;
       
procedure queryL ( l , r , k : longint );
    var
        min , mid , max , tmp : longint;
    begin
        min := totmin;
        max := totmax;
        tmp := findL ( 1 , l , r , min );
        if k <= tmp then begin
            writeln ( min );
            exit;
        end;
        while max-min>1 do begin
            mid := (min+max)shr 1;
            tmp := findL ( 1 , l , r , mid );
            if k > tmp then min := mid