线段树套SBT。。【宋壬初吧】

直接发了。。
program p1665;
type
    sbtnode=record
        lsb,rsb,key,s:longint;
        end;
    intervaltree=record
        tot,root,lc,rc:longint;
        l,r,m,d:longint;
        end;
var
    ctree:array[0..150003]of intervaltree;
    sbt:array[1..18,0..100002]of sbtnode;
    flag:boolean;
    a:array[1..50001]of longint;
    top:longint;
    n,mm,i,ii:longint;
    mid,o,v,lll,rrr,l,r,tt,k,max:longint;
    ch:char;
////////////////---sbt LR;
procedure lr(p:longint;var t:longint);
var
    k:longint;
begin
    k:=sbt[p,t].rsb;
    sbt[p,t].rsb:=sbt[p,k].lsb;
    sbt[p,k].lsb:=t;
    sbt[p,k].s:=sbt[p,t].s;
    sbt[p,t].s:=sbt[p,sbt[p,t].lsb].s+sbt[p,sbt[p,t].rsb].s+1;
    t:=k;
end;
/////////////////---sbt RR;
procedure rr(p:longint;var t:longint);
var
    k:longint;
begin
    k:=sbt[p,t].lsb;
    sbt[p,t].lsb:=sbt[p,k].rsb;
    sbt[p,k].rsb:=t;
    sbt[p,k].s:=sbt[p,t].s;
    sbt[p,t].s:=sbt[p,sbt[p,t].lsb].s+sbt[p,sbt[p,t].rsb].s+1;
    t:=k;
end;
/////////////////---sbt Maintain;
procedure maintain(p:longint;var t:longint;ff:boolean);
begin
    if ff then
        begin
            if sbt[p,sbt[p,sbt[p,t].lsb].lsb].s>
                sbt[p,sbt[p,t].rsb].s then
                rr(p,sbt[p,t].lsb)
            else
            if sbt[p,sbt[p,sbt[p,t].lsb].rsb].s>
                sbt[p,sbt[p,t].rsb].s then
                begin
                    lr(p,sbt[p,t].lsb);
                    rr(p,t);

送TA礼物

IP属地:上海

1楼2009-10-08 20:40回复

                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);

IP属地:上海

2楼2009-10-08 20:40

    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);

IP属地:上海

3楼2009-10-08 20:40

                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

IP属地:上海

4楼2009-10-08 20:40

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;

IP属地:上海

5楼2009-10-08 20:40

    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

IP属地:上海

6楼2009-10-08 20:40

                                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.

IP属地:上海

7楼2009-10-08 20:40

用C/C++的话应该会更好看一点。

IP属地:上海

19楼2011-02-17 14:13

日	一	二	三	四	五	六

线段树套SBT。。

登录百度账号

扫二维码下载贴吧客户端