题解 P2617 【Dynamic Rankings】

· · 题解

动态排名-主席树套树状数组

首先谈一下主席树套树状数组。我个人的理解是,因为普通的静态主席树是维护的一个前缀和,第i个根是第i-1个根的继承。自从套上树状数组以后,第i个根就应该是i到i-lowbit(i)....(一直减,先树状数组那样).....1的继承。这样子有什么好处?如果我们改变了一个值,那么它只需要影响到log\ n个树链,每一个树链是只有log\ n个节点的,我们的修改、查询就降到了(log\ n)^2。

照大佬们Query写的非递归版。因为chen\ zhe大佬改了数据,本人的离散化直接崩溃,所以现在是50分,原来的100分。由于有修改,离散化的时候就直接全部读进来,然后离散化。

不离散化    普通的离散化     

 25分          50分

需要神奇的离散化。

Code

// luogu-judger-enable-o2

var
    root,num,sortn,xx,yy,recf:array[-1..310000] of longint;
    left,right,value:array[-1..2100009] of longint;
    ques:array[1..3,-1..310000] of longint;
    bucket:array[-1..100000009] of longint;
    mode:array[-1..310000] of char;
    cnt,i,j,n,m,add,tail,head:longint;

procedure Sort(l,r:longint);
var
    i,j,s,t:longint;
begin
    i:=l; j:=r; s:=sortn[(l+r) div 2];
    repeat
        while sortn[i]<s do inc(i); while sortn[j]>s do dec(j);
        if i<=j then
        begin t:=sortn[i]; sortn[i]:=sortn[j]; sortn[j]:=t; inc(i); dec(j);
        end;
    until i>=j;
    if i<r then Sort(i,r);
    if j>l then Sort(l,j);
end;

function lowbit(num:longint):longint; begin exit(num and -num); end;

procedure swap(var x,y:longint); begin x:=x xor y; y:=x xor y; x:=x xor y; end;

procedure Build(var now:longint;l,r,key:longint);
var
    mid:longint;
begin
    if now=0 then
    begin inc(cnt); now:=cnt;
    end;
    inc(value[now],add);
    if l=r then exit;

    mid:=(l+r) div 2;
    if (key<=mid) then Build(left[now],l,mid,key)
    else Build(right[now],mid+1,r,key);
end;

procedure Change(x,y:longint);
var
    i:longint;
begin
    add:=-1; i:=x;
    while i<=n do begin Build(root[i],0,300009,bucket[num[x]]); inc(i,lowbit(i)); end;

    add:=1; i:=x;
    while i<=n do begin Build(root[i],0,300009,bucket[y]); inc(i,lowbit(i)); end;
    num[x]:=y;
end;

function Query(x,y,k:longint):longint;
var
    t1,t2,l,r,temp,mid,i:longint;
begin
    dec(x); swap(x,y);
    t1:=0; t2:=0;
    i:=x;
    while i>=1 do begin inc(t1); xx[t1]:=root[i]; dec(i,lowbit(i)); end;
    i:=y;
    while i>=1 do begin inc(t2); yy[t2]:=root[i]; dec(i,lowbit(i)); end;

    l:=0; r:=300009;
    while l<r do
    begin
        temp:=0;
        mid:=(l+r) div 2;
        for i:=1 to t1 do inc(temp,value[left[xx[i]]]);
        for i:=1 to t2 do dec(temp,value[left[yy[i]]]);
        if k<=temp then
        begin
            for i:=1 to t1 do xx[i]:=left[xx[i]];
            for i:=1 to t2 do yy[i]:=left[yy[i]];
            r:=mid;
        end
        else
        begin
            for i:=1 to t1 do xx[i]:=right[xx[i]];
            for i:=1 to t2 do yy[i]:=right[yy[i]];
            dec(k,temp); l:=mid+1;
        end;
    end;
    exit(recf[l]);
end;

begin
    readln(n,m);
    for i:=1 to n do read(num[i]); sortn:=num; readln;
    for i:=1 to m do begin read(mode[i]);
        if mode[i]='Q' then
            readln(ques[1,i],ques[2,i],ques[3,i])
        else
        begin
            readln(ques[1,i],ques[2,i]); 
            inc(tail); sortn[tail+n]:=ques[2,i];
        end; end;

    Sort(1,n+tail); head:=0;
    for i:=1 to n+tail do
        if sortn[i]<>sortn[i-1] then 
        begin
            inc(head);
            bucket[sortn[i]]:=head; recf[head]:=sortn[i];
        end;

    for i:=1 to n do
    begin
        add:=1; j:=i;
        while j<=n do begin Build(root[j],0,300009,bucket[num[i]]); inc(j,lowbit(j)); end;
    end;
    for i:=1 to m do
        if mode[i]='Q' then
            writeln(Query(ques[1,i],ques[2,i],ques[3,i])) else Change(ques[1,i],ques[2,i]);
end.

有不懂的可以直接踢出提出,欢迎死心私信。