equance]伸展树Splay & 平衡树SBT(下)

现在的位置: 首页 > 综合 > 正文

RSS

equance]伸展树Splay & 平衡树SBT(下)

2017年11月03日 ⁄ 综合 ⁄ 共 31088字 ⁄ 字号小中大 ⁄ 评论关闭

[

[PKU 3481][Noi 2004 Cashier]伸展树Splay & 平衡树SBT(上)

{

本文主要介绍一下伸展树与平衡树SBT

平衡树应用广泛效率极高（最坏为Logn）

是实现优先队列数据字典的不二选择

伸展树因其独有的Splay操作

可以应对很多线段树难以处理的区间问题

而不仅仅是用作一棵排序二叉树来处理数据

而且伸展树效率也很高达到了均摊Logn的级别

}

先讲平衡树SBT

CQF大神的SBT我已经膜拜好久了

程序也差不多看懂了

果然是大神的程序很精简

有些地方在论文里没有解释

在这里讲一下

先是旋转(zig|zag)

1 procedure right_rotate(var t:longint);//右旋 使用变量参数 方便操作
2  begin
3    k:=left[t];
4    left[t]:=right[k];
5    right[k]:=t;
6    s[k]:=s[t];
7    s[t]:=s[left[t]]+s[right[t]]+1;
8    t:=k;//根节点改变 更新变参
9  end;

1 procedure left_rotate(var t:longint);//左旋
2  begin
3    k:=right[t];
4    right[t]:=left[k];
5    left[k]:=t;
6    s[k]:=s[t];
7    s[t]:=s[left[t]]+s[right[t]]+1;
8    t:=k;
9  end;

由于两个旋转是对称的就单讲一个右旋

前三句话很好理解是旋转需要的指针变动

第6行更新新的根节点k的size域就是原来根节点t的size

第7行更新t节点的size域此时儿子已经改变且size域已经求好所以通过儿子计算即可

最后一行比较难理解{t:=k;}

这里因为t是传的变量参数相当于是传递的记录当前子树的根的变量

于是k旋转上去之后子树的根也应当自动更新

(空讲不一定清楚在后文讨论其他函数的时候会再次具体说明)

下来是插入(Insert)

 1 procedure insert(var t,v:longint);//同样使用变参
 2  begin
 3    if t=0 then begin
 4       inc(tt);
 5       t:=tt;//使用变参之后 节点父亲的儿子指针也会同时改变
 6       key[t]:=v;
 7       s[t]:=1;
 8       left[t]:=0;
 9       right[t]:=0; //到达边界 新建节点
10    end
11    else begin
12       inc(s[t]);//注意更新size
13       if v<key[t] then
14          insert(left[t],v)
15       else
16          insert(right[t],v);
17       maintain(t,v>=key[t]);
18    end;
19  end;

第3行如果当前子树为空树则新建节点为其根

其中有一句{t:=tt;}这一句是有用的

我们看到t是传递的变量这个变量是什么呢?

递归退回到上一层我们看到是l[x]或r[x]

这里改变t为tt 事实上就是改变l[x]或r[x] 这里也就是传递变参的高明之处

不用记录父亲直接可以改变父亲节点的儿子指针

这样代码便会简洁许多

回到上面旋转留下的问题

由于插入以及后面的删除 maintain函数都使用了变参

旋转作为最基础的操作也应当使用变参

事实上利用变参不仅可以传递值还传递指针的特性

可以使很多代码得以简化 但是对思考的细致有要求

下来考虑maintain函数

 1 procedure maintain(var t:longint;flag:boolean);//保持SBT性质
 2  begin
 3    if flag=false then//用boolean变量flag决定调整左子树还是右子树
 4       if s[left[left[t]]]>s[right[t]] then
 5          right_rotate(t)
 6       else
 7          if s[right[left[t]]]>s[right[t]] then begin
 8             left_rotate(left[t]);
 9             right_rotate(t);
10          end
11          else
12             exit
13    else
14       if s[right[right[t]]]>s[left[t]] then
15          left_rotate(t)
16       else
17          if s[left[right[t]]]>s[left[t]] then begin
18             right_rotate(right[t]);
19             left_rotate(t);
20          end//此处各种情况在论文里有详细说明
21          else
22             exit;//无需调整 直接退出
23    maintain(left[t],false);//递归调整性质可能被破坏的子树
24    maintain(right[t],true);//优化：只调整左子树的左子树和右子树的右子树
25    maintain(t,true);
26    maintain(t,false);//调整自身
27  end;

maintain在论文里讲的很详细不再细说

这个函数能达到O(1)的复杂度

(膜拜CQF大神怎么想到的)

下面是删除(Delete)

 1 function delete(var t:longint;v:longint):longint;
　　//这里的删除必定会删掉一个节点并返回这个节点
 2  begin
 3    dec(s[t]);
 4    if (v=key[t])or(v<key[t])and(left[t]=0)or(v>key[t])and(right[t]=0) then begin
 5       delete:=key[t];//到达边界 删除一个节点 返回值
 6       if (left[t]=0)or(right[t]=0) then
 7          t:=left[t]+right[t]-0//直接删除
 8       else
 9          key[t]:=delete(left[t],key[t]+1);//从右子树中取下一个最大的节点取代当前节点
10    end
11    else
12       if v<key[t] then
13          delete:=delete(left[t],v)
14       else
15          delete:=delete(right[t],v);
16  end;//这里不用maintain 因为删除不增加高度

CQF的删除我一开始也没看懂

我一直在想删除一定会删掉一个节点不会出错么

事实上这种"暴力"的删法相当巧妙

至于怕删错用下面的find函数特判即可

第一句话由于必定删除一个节点不由分说讲这个子树的size减1

　　　　我们看到如果不是必定删除一个的话 size值减不减一还是个麻烦的事

第2行:有几种情况是必须在这里把根节点砍掉的

　　比如要删的值小于当前节点而左子树为空

　　要删的值大于当前节点而右子树为空

　　抑或是当前节点是要删的节点

我们注意到这样我们删的节点的值必然是最接近于我们想删的值的

下面分情况讨论怎么删

　　一是只有一个子树直接把儿子连到父亲即可

　　二是由2个子树就从左子树挖一个最大的填到当前子树根上

　　　　根据上面最接近于我们想删的值的结论

　　　　所以递归调用删除key[x]+1必然是删的左子树最大节点

第11行不符合上面任何一个情况递归删除

最后由于删除不增加高度 maintain也可以省了

下面是各个查询函数(Find Rank Select Pred Succ)

 1 function find(var t,v:longint):boolean;//以下可以不用变参 因为是查询操作
 2  begin
 3    if t=0 then
 4       exit(false);//没有查询到
 5    if v<key[t] then
 6       find:=find(left[t],v)
 7    else
 8       find:=(key[t]=v)or find(right[t],v);//递归
 9  end;
10  function rank(var t,v:longint):longint;
11  begin
12    if t=0 then
13       exit(1);//子树为空时 所查节点排位自然为1
14    if v<=key[t] then
15       rank:=rank(left[t],v)
16    else
17       rank:=s[left[t]]+1+rank(right[t],v);//向右子树查询 注意右子树中的排位不是真是排位
18  end;
19  function select(var t:longint;k:longint):longint;
20  begin
21    if k=s[left[t]]+1 then
22       exit(key[t]);//查询节点为根
23    if k<=s[left[t]] then
24       select:=select(left[t],k)
25    else
26       select:=select(right[t],k-1-s[left[t]]);//向右子树查询 注意同rank
27  end;
28  function pred(var t,v:longint):longint;
29  begin
30    if t=0 then
31       exit(v);//到达边界 即 所查节点没有前驱直接返回所查节点
32    if v<=key[t] then
33       pred:=pred(left[t],v)//前驱必在左子树上
34    else begin
35       pred:=pred(right[t],v);
36       if pred=v then//在右子树上没有前驱 即 所查节点为右子树上最小
37          pred:=key[t];//前驱为根
38    end;
39  end;
40  function succ(var t,v:longint):longint;
41  begin
42    if t=0 then
43       exit(v);
44    if key[t]<=v then
45       succ:=succ(right[t],v)
46    else begin
47       succ:=succ(left[t],v);
48       if succ=v then
49          succ:=key[t];//后继和查前驱类似
50    end;
51  end;

注释比较清楚就不细写了

需要注意查询的边界条件比如Rank的边界:空树中返回1

实质上Rank是将所查节点假设插入后的rank值返回

比如{1,2,4,5}中 6的rank是5,0的rank是1,3的rank是3,4的rank是3

自然而然在一个空集{}中任何数的rank都是1

succ和pred在遇到空树时返回v

也是假设插入后取前驱后继

当为最大最小值时直接返回最大最小值

比如{1,2,4,5}中 6的pred是5,0的pred是0,3的pred是2,4的pred是2

所以{}中任何数的前驱后继是其本身

最后是主函数(main)

 1 begin
 2    tt:=0;//总节点数
 3    t:=0;//用t纪录数组中的当前根节点 根节点作为变参传递时 根据需要会随时改变（向前移动）
 4    s[0]:=0;//空点初始size为0
 5    for q:=1 to q do
 6       case a[q] of//由于删除等操作必定删除一个节点或返回值 有必要时应先确定所查节点是否在树中
 7          1:insert(t,b[q]);
 8          2:if find(t,b[q]) then delete(t,b[q]);
 9          3:writeln(find(t,b[q]));
10          4:writeln(rank(t,b[q]));
11          5:writeln(select(t,b[q]));
12          6:writeln(pred(t,b[q]));
13          7:writeln(succ(t,b[q]));
14       end;
15 end;
16 begin
17    assign(input,'input.txt');
18    assign(output,'ans0.txt');
19    reset(input);
20    rewrite(output);
21    init;
22    work;
23    close(input);
24    close(output);
25 end.

注释清楚注意s[0]与t和tt的含义

最后给出完整的陈启峰官方SBT代码

CQF_SBT

Noi2004郁闷的出纳员是可以运用SBT解决的

只需注意工资是整体上浮下调的

我们累加工资的调整代数和记录差值delta

比如工资涨了5 又降了7 delta=-2

当前工资底线需要时时改变总工资涨10 底线就要扣10 而员工工资不需整体改变

比如原来工资底线为8 现在要按8-(-2)=10来算

而对于新来的员工出始工资统一减delta即可

还要注意要删除的是一棵一棵的子树不要一个一个去删

代码如下

const   maxn=200000;
var    l,r,s,n:array[0..maxn]of longint;
   k,i,tt,ans,t,d,m,min:longint;
   ch:char;
procedure zig(var x:longint);
var y:longint;
begin
y:=l[x]; l[x]:=r[y]; r[y]:=x;
s[y]:=s[x]; s[x]:=s[l[x]]+s[r[x]]+1;
x:=y;
end;
procedure zag(var x:longint);
var y:longint;
begin
y:=r[x]; r[x]:=l[y]; l[y]:=x;
s[y]:=s[x]; s[x]:=s[l[x]]+s[r[x]]+1;
x:=y;
end;
procedure maintain(var x:longint; flag:boolean);
begin
if flag
   then begin
   if s[l[l[x]]]>s[r[x]] then zig(x)
       else if s[l[r[x]]]>s[r[x]]
           then begin zag(l[x]); zig(x); end
           else exit;
   end
   else begin
   if s[r[r[x]]]>s[l[x]] then zag(x)
       else if s[r[l[x]]]>s[l[x]]
           then begin zig(r[x]); zag(x); end
           else exit;
   end;
maintain(l[x],true); maintain(r[x],false);
maintain(x,true);maintain(x,false);
end;
procedure insert(var x:longint; v:longint);
begin
if x=0
   then begin
   inc(tt); x:=tt;
   n[x]:=v; s[x]:=1;
   end
   else begin
   inc(s[x]);
   if v<n[x] then insert(l[x],v)
       else insert(r[x],v);
   maintain(x,v<=n[x]);
   end;
end;
function delete(var x:longint):longint;
var     y:longint;
begin
if x=0 then exit(0);
if n[x]<min
   then begin
   y:=s[l[x]]+1; l[x]:=0;
   y:=y+delete(r[x]);
       s[x]:=s[x]-y;
   s[r[x]]:=s[x]; x:=r[x];
   end
   else begin
   y:=delete(l[x]);
   s[x]:=s[x]-y;
   end;
delete:=y;
end;
function select(x,k:longint):longint;
begin
if k=s[l[x]]+1 then exit(n[x]+d);
if k<s[l[x]]+1 then exit(select(l[x],k))
   else exit(select(r[x],k-s[l[x]]-1));
end;
begin
assign(input,'cashier.in'); reset(input);
assign(output,'cashier.out'); rewrite(output);
d:=0; t:=0; tt:=0; s[0]:=0;
readln(m,min); ans:=0;
for i:=1 to m do
   begin
   readln(ch,k);
   case ch of
       'I':    begin
           ans:=ans+delete(t);
           if k-d>=min then insert(t,k-d);
           end;
       'A':    begin d:=d+k; min:=min-k; end;
       'S':    begin d:=d-k; min:=min+k; ans:=ans+delete(t); end;
       'F':    begin
           ans:=ans+delete(t);
           if s[t]<k then writeln(-1)
               else writeln(select(t,s[t]-k+1));
           end;
       end;
   end;
writeln(ans);
close(input); close(output);
end.


PKU3481是平衡树的裸题

伸展树有时候可以作为一个平衡树的替代

这题没有恶心数据伸展树很快

给个伸展树代码吧也算承上启下了

const    maxn=300000;
var    m,n,l,r,f:array[0..maxn]of longint;
   root,tt,k,p,q:longint;
procedure zig(var x:longint);
var    y:longint;
begin
y:=l[x]; l[x]:=r[y]; r[y]:=x;
f[y]:=f[x]; f[x]:=y;
if l[x]<>0 then f[l[x]]:=x;
x:=y;
end;
procedure zag(var x:longint);
var    y:longint;
begin
y:=r[x]; r[x]:=l[y]; l[y]:=x;
f[y]:=f[x]; f[x]:=y;
if r[x]<>0 then f[r[x]]:=x;
x:=y;
end;
procedure splay(var x:longint);
begin
while f[x]<>0 do
   if l[f[x]]=x
       then begin
       if f[f[x]]=0
           then zig(root)
           else if l[f[f[x]]]=f[x]
               then zig(l[f[f[x]]])
               else zig(r[f[f[x]]]);
       end
       else begin
       if f[f[x]]=0
           then zag(root)
           else if l[f[f[x]]]=f[x]
               then zag(l[f[f[x]]])
               else zag(r[f[f[x]]]);
       end;
end;
procedure insert(var x:longint; k,p:longint);
var    i,j:longint;
begin
if x=0
   then begin
   inc(tt); x:=tt;
   n[x]:=p; m[x]:=k;
   exit;
   end;
j:=x;
while j<>0 do
   begin
   i:=j;
   if p<n[i] then j:=l[i] else j:=r[i];
   end;
inc(tt); j:=tt;
n[j]:=p; m[j]:=k;
f[j]:=i; l[j]:=0; r[j]:=0;
if p<n[i] then l[i]:=j else r[i]:=j;
splay(j);
end;
procedure deletemin(var x:longint);
var    i:longint;
begin
if x=0
   then begin writeln(0); exit; end;
i:=x;
while l[i]<>0 do i:=l[i];
writeln(m[i]);
splay(i);
x:=r[i]; f[r[i]]:=0;
end;
procedure deletemax(var x:longint);
var    i:longint;
begin
if x=0 
   then begin writeln(0); exit; end;
i:=x;
while r[i]<>0 do i:=r[i];
writeln(m[i]);
splay(i);
x:=l[i]; f[l[i]]:=0;
end;
begin
assign(input,'dq.in'); reset(input);
assign(output,'dq.out'); rewrite(output);
read(q);
tt:=0; root:=0;
while q<>0 do
   begin
   case q of
       1:    begin
           readln(k,p);
           insert(root,k,p);
           end;
       2:    deletemax(root);
       3:    deletemin(root);
       end;
   read(q);
   end;
close(input); close(output);
end.


在第二部分里我们介绍伸展树(Splay Tree)

先贴一下我自己写的伸展树代码不长也比较快

(我只用了单旋来Splay 但是好像不比双旋慢)

const    maxn=2000000;
var    l,r,f,n:array[0..maxn]of longint;
   order,root,m,i,k,tt,t:longint;
procedure zig(var x:longint);
var    y:longint;
begin
y:=l[x]; l[x]:=r[y]; r[y]:=x;
f[y]:=f[x]; f[x]:=y;
if l[x]<>0 then f[l[x]]:=x;
x:=y;
end;
procedure zag(var x:longint);
var    y:longint;
begin
y:=r[x]; r[x]:=l[y]; l[y]:=x;
f[y]:=f[x]; f[x]:=y;
if r[x]<>0 then f[r[x]]:=x;
x:=y;
end;
procedure splay(var x,S:longint);
begin
while f[x]<>f[S] do
   if l[f[x]]=x
       then begin
       if f[x]=S
           then zig(S)
           else if l[f[f[x]]]=f[x]
               then zig(l[f[f[x]]])
               else zig(r[f[f[x]]]);
       end
       else begin
       if f[x]=S
           then zag(S)
           else if l[f[f[x]]]=f[x]
               then zag(l[f[f[x]]])
               else zag(r[f[f[x]]]);
       end;
end;
function find(x,v:longint):boolean;
begin
if x=0 then exit(false);
if v=n[x] then exit(true);
if v<n[x]
   then find:=find(l[x],v)
   else find:=find(r[x],v);
end;
procedure insert(var x:longint; v:longint);
var    i,j:longint;
begin
if x=0
   then begin
   inc(tt); x:=tt;
   l[x]:=0; r[x]:=0; f[x]:=0;
   n[x]:=v;
   exit; end;
j:=x;
while j<>0 do
   begin
   i:=j;
   if v<=n[i] then j:=l[i] else j:=r[i];
   end;
inc(tt); j:=tt;
if v<=n[i] then l[i]:=j else r[i]:=j;
f[j]:=i; n[j]:=v;
splay(j,root);
end;
procedure join(var x,y:longint);
var    i,j:longint;
begin
if (x=0)or(y=0)
   then begin
   x:=x+y;
   exit; end;
i:=x; j:=y;
while r[i]<>0 do i:=r[i];
while l[j]<>0 do j:=l[j];
splay(i,x); splay(j,y);
r[i]:=j; f[j]:=i;
x:=i;
end;
procedure delete(var x:longint; v:longint);
var    i,j:longint;
begin
i:=x;
while (i<>0)and(n[i]<>v) do
   if v<n[i] then i:=l[i] else i:=r[i];
if i=0 then exit;
splay(i,root);
join(l[i],r[i]);
x:=l[i]; f[l[i]]:=0;
end;
begin
assign(input,'input.txt'); reset(input);
assign(output,'ans.txt'); rewrite(output);
readln(m);
tt:=0; root:=0;
for i:=1 to m do
   begin
   readln(order,k);
   case order of
       1:insert(root,k);
       2:delete(root,k);
       3:writeln(find(root,k));
       end;
   end;
close(input); close(output);
end.


BOB HAN原创转载请注明出处

BOB HAN 原创转载请注明出处 http://www.cnblogs.com/Booble/

标签: 平衡树, Splay, SBT, 伸展树

PKU 3580 3468][Noi 2005 Sequance]伸展树Splay & 平衡树SBT(下)

{

承上一部分

}

我们在上半部分说到伸展树不是用来作为平衡树使用的

而应当将它的Splay操作发扬光大

我们先来讨论一下Splay操作

splay操作的具体实现可以从杨思雨的论文里了解

不过我找到的论文只有pdf和ppt(汗)

于是就去看splay的算法

看的云里雾里只知道splay是一个提根操作

还要分六种情况讨论(大汗)

我觉得直接单旋提根也不会差多少

编程复杂度还低

于是引用杨思雨论文里的一句话

……不能只一味的追求算法有很高的时间效率，而需要在时间复杂度、空间复杂度、编程复杂度三者之间找到一个“平衡点”……

于是我就选择了只用单旋来实现splay

这段程序是我自己设计实现的但是总觉得和双旋的代码有某种相似(巨汗)

(其实应当算作是殊途同归吧)

贴个代码先

 1 procedure zig(var x:longint);
 2  var    y:longint;
 3  begin
 4 y:=l[x]; l[x]:=r[y]; r[y]:=x;
 5 f[y]:=f[x]; f[x]:=y;
 6  if l[x]<>0 then f[l[x]]:=x;
 7 x:=y;
 8  end;
 9  procedure zag(var x:longint);
10  var    y:longint;
11  begin
12 y:=r[x]; r[x]:=l[y]; l[y]:=x;
13 f[y]:=f[x]; f[x]:=y;
14  if r[x]<>0 then f[r[x]]:=x;
15 x:=y;
16  end;
17  procedure splay(var x,S:longint);
18  begin
19  while f[x]<>f[S] do
20     if l[f[x]]=x
21         then begin
22         if f[x]=S
23             then zig(S)
24             else if l[f[f[x]]]=f[x]
25                 then zig(l[f[f[x]]])
26                 else zig(r[f[f[x]]]);
27         end
28         else begin
29         if f[x]=S
30             then zag(S)
31             else if l[f[f[x]]]=f[x]
32                 then zag(l[f[f[x]]])
33                 else zag(r[f[f[x]]]);
34         end;
35  end;

可以看到

splay需要两个子过程左旋和右旋

　　splay还是一个两个参数的函数其中x是所提的节点 S是所在子树的根节点 也就是x最后所在的位置

　　x是值参 S是变参 (这里给x也是变参不过没什么区别的)

为了自底向上splay 我们还需记录父亲节点即f 数组

旋转和SBT类似就多了2句更新父亲的话

具体分析一下splay函数

　　19行一个while循环将x旋转直到x为子树的根

　　20行判断x是其父亲的左儿子还是右儿子根据左右情况决定左旋还是右旋

　　左右是对称的我们具体讨论是父亲的左儿子的情况

　　　　21行判断是父亲否为根如果为根直接旋转根

　　　　否则继续讨论父亲是否是祖父的左儿子是则旋转祖父的左儿子否则旋转祖父的右儿子

　　这里兜了一个圈子祖父的儿子不就是父亲么?

　　其实不然在程序中f[x]和l[f[f[x]]]或r[f[f[x]]]虽然是同一个值但不是同一个变量

　　我们看到旋转函数的参数是一个变参于是考虑这个参数是哪一个变得很重要否则就会出错

　　我们回想SBT的旋转在SBT中我们旋转的参数是l[x]或r[x]

　　那么在这里同理我们也应当用儿子指针当参数而不是父亲指针

　　我们使用变参的初衷是为了免去修改节点的同时修改节点父亲的儿子指针的过程

　　于是splay的旋转也应当传递节点父亲的儿子指针并在最后使用x:=y来修改

这样一个splay函数就完成了

经过测试这样和双旋的时间差不了多少

其实很方便的

测试时我用的是记录size域的splay(单旋双旋)和SBT

对于1000000次操作的随机数据SBT是5s+ splay差不多都是7s+

可见splay常数确实大作为自平衡的排序二叉树使用确实不如SBT

也可以发现单旋还是很实用的

贴一下带size域的splay(支持的各项操作和SBT一致)

  1 const    max=300000;
  2  var    f,l,r,s,n:array[0..max]of longint;
  3     stack:array[1..max]of longint;
  4     top,tt,root,i,m,order,k:longint;
  5  procedure zig(var x:longint);
  6  var    y:longint;
  7  begin
  8 y:=l[x]; l[x]:=r[y]; r[y]:=x;
  9 f[y]:=f[x]; f[x]:=y;
 10  if l[x]<>0 then f[l[x]]:=x;
 11 s[y]:=s[x]; s[x]:=s[l[x]]+s[r[x]]+1;
 12 x:=y;
 13  end;
 14  procedure zag(var x:longint);
 15  var    y:longint;
 16  begin
 17 y:=r[x]; r[x]:=l[y]; l[y]:=x;
 18 f[y]:=f[x]; f[x]:=y;
 19  if r[x]<>0 then f[r[x]]:=x;
 20 s[y]:=s[x]; s[x]:=s[l[x]]+s[r[x]]+1;
 21 x:=y;
 22  end;
 23  procedure splay(x:longint; var S:longint);
 24  begin
 25  while f[x]<>f[S] do
 26     if l[f[x]]=x
 27         then begin
 28         if f[x]=S
 29             then zig(S)
 30             else if l[f[f[x]]]=f[x]
 31                 then zig(l[f[f[x]]])
 32                 else zig(r[f[f[x]]]);
 33         end
 34         else begin
 35         if f[x]=S
 36             then zag(S)
 37             else if l[f[f[x]]]=f[x]
 38                 then zag(l[f[f[x]]])
 39                 else zag(r[f[f[x]]]);
 40         end;
 41  end;
 42  procedure newnode(var x:longint);
 43  begin
 44  if top>0
 45     then begin x:=stack[top]; dec(top); end
 46     else begin inc(tt); x:=tt; end;
 47 f[x]:=0; l[x]:=0; r[x]:=0;
 48  end;
 49  procedure clrnode(var x:longint);
 50  begin
 51 inc(top); stack[top]:=x;
 52  end;
 53  procedure insert(var x:longint; v:longint);
 54  var    i,j:longint;
 55  begin
 56  if x=0
 57     then begin
 58     newnode(x);
 59     n[x]:=v; s[x]:=1;
 60     exit; end;
 61 j:=x;
 62  while j<>0 do
 63     begin
 64     i:=j;
 65     inc(s[i]);
 66     if v<=n[i] then j:=l[i] else j:=r[i];
 67     end;
 68 newnode(j);
 69  if v<=n[i] then l[i]:=j else r[i]:=j;
 70 n[j]:=v; s[j]:=1; f[j]:=i;
 71 splay(j,x);
 72  end;
 73  procedure join(var x,y:longint);
 74  var    i,j:longint;
 75  begin
 76  if (x=0)or(y=0)
 77         then begin
 78         x:=x+y;
 79         exit; end;
 80 i:=x; j:=y;
 81  while r[i]<>0 do i:=r[i];
 82  while l[j]<>0 do j:=l[j];
 83 splay(i,x); splay(j,y);
 84 r[i]:=j; f[j]:=i;
 85 s[i]:=s[i]+s[j];
 86 x:=i;
 87  end;
 88  procedure delete(var x:longint; v:longint);
 89  var    i,j:longint;
 90  begin
 91 i:=x;
 92  while (i<>0)and(n[i]<>v) do
 93     if v<n[i] then i:=l[i] else i:=r[i];
 94  if i=0 then exit;
 95 splay(i,x);
 96 join(l[i],r[i]);
 97 j:=x; x:=l[i]; f[x]:=f[j];
 98 clrnode(j);
 99  end;
100  function find(x,v:longint):boolean;
101  begin
102  if x=0 then exit(false);
103  if v=n[x] then exit(true);
104  if v<n[x]
105     then find:=find(l[x],v)
106     else find:=find(r[x],v);
107  end;
108  function rank(x,v:longint):longint;
109  begin
110  if x=0 then exit(1);
111  if v<=n[x]
112     then rank:=rank(l[x],v)
113     else rank:=rank(r[x],v)+1+s[l[x]];
114  end;
115  function select(x,k:longint):longint;
116  begin
117  if s[l[x]]+1=k then exit(n[x]);
118  if k<=s[l[x]]
119     then select:=select(l[x],k)
120     else select:=select(r[x],k-s[l[x]]-1);
121  end;
122  function pred(x,v:longint):longint;
123  begin
124  if x=0 then exit(v);
125  if v<=n[x]
126     then pred:=pred(l[x],v)
127     else begin
128     pred:=pred(r[x],v);
129     if pred=v then pred:=n[x];
130     end;
131  end;
132  function succ(x,v:longint):longint;
133  begin
134  if x=0 then exit(v);
135  if v>=n[x]
136     then succ:=succ(r[x],v)
137     else begin
138     succ:=succ(l[x],v);
139     if succ=v then succ:=n[x];
140     end;
141  end;
142  begin
143 assign(input,'bst.in'); reset(input);
144 assign(output,'bst.out'); rewrite(output);
145 readln(m);
146 root:=0; tt:=0; s[0]:=0; top:=0;
147  for i:=1 to m do
148     begin
149     readln(order,k);
150     case order of
151         1:insert(root,k);
152         2:delete(root,k);
153         3:writeln(find(root,k));
154         4:writeln(rank(root,k));
155         5:if k<=s[root] then writeln(select(root,k))
156             else writeln(-1);
157         6:writeln(pred(root,k));
158         7:writeln(succ(root,k));
159         end;
160     end;
161 close(input); close(output);
162  end.
163

//2010-11-9 更新优化过的代码

//Splay Tree To Deal with Repeated Node
//21~11 2010-11-9
const    maxn=500000;
var    stack,l,r,n,s,t,f:array[0..maxn]of longint;
    tt,top,root,i,q,c,x:longint;

//Splay(x,S);
procedure zig(var x:longint);
var    y:longint;
begin
y:=l[x]; l[x]:=r[y]; r[y]:=x;
f[y]:=f[x]; f[x]:=y;
if l[x]<>0 then f[l[x]]:=x;
s[y]:=s[x]; s[x]:=s[l[x]]+s[r[x]]+t[x];
x:=y;
end;
procedure zag(var x:longint);
var    y:longint;
begin
y:=r[x]; r[x]:=l[y]; l[y]:=x;
f[y]:=f[x]; f[x]:=y;
if r[x]<>0 then f[r[x]]:=x;
s[y]:=s[x]; s[x]:=s[l[x]]+s[r[x]]+t[x];
x:=y;
end;
procedure splay(x:longint; var S:longint);
begin
while f[x]<>f[S] do
    if l[f[x]]=x
        then if f[x]=S then zig(S)
            else if l[f[f[x]]]=f[x]
                then zig(l[f[f[x]]])
                else zig(r[f[f[x]]])
        else if f[x]=S then zag(S)
            else if l[f[f[x]]]=f[x]
                then zag(l[f[f[x]]])
                else zag(r[f[f[x]]]);
end;

//New and Dispose a Node
procedure newnode(var x:longint);
begin
if top=0
    then begin
    inc(tt);
    x:=tt;
    end
    else begin
    x:=stack[top];
    dec(top);
    end;
end;
procedure disnode(x:longint);
begin
inc(top);
stack[top]:=x;
end;

//FindIt FindMax FindMin
function find(v:longint):boolean;
var    i:longint;
begin
i:=root;
while i<>0 do
    begin
    if n[i]=v
        then begin
        splay(i,root);
        exit(true);
        end;
    if v<n[i] then i:=l[i]
        else i:=r[i];
    end;
find:=false;
end;
function max(var x:longint):longint;
var    i:longint;
begin
i:=x;
while r[i]<>0 do
    i:=r[i];
max:=n[i];
splay(i,x);
end;
function min(var x:longint):longint;
var    i:longint;
begin
i:=x;
while l[i]<>0 do
    i:=l[i];
min:=n[i];
splay(i,x);
end;

//Insert Delete Union
procedure insert(v:longint);
var    i,j,x:longint;
begin
if find(v)
    then begin
    inc(t[root]);
    inc(s[root]);
    end
    else begin
    newnode(x);
    f[x]:=0; l[x]:=0; r[x]:=0;
    n[x]:=v; s[x]:=1; t[x]:=1;
    if root=0
        then root:=x
        else begin
        i:=root; j:=root;
        while i<>0 do
            begin
            inc(s[i]); j:=i;
            if v<n[i] then i:=l[i]
                else i:=r[i];
            end;
        if v<n[j] then l[j]:=x
            else r[j]:=x;
        f[x]:=j;
        splay(x,root);
        end;
    end;
end;
function union(var x,y:longint):longint;
begin
if x=0
    then begin
    f[y]:=0;
    exit(y);
    end;
max(x);
f[x]:=0; r[x]:=y; f[y]:=x;
s[x]:=s[l[x]]+s[r[x]]+t[x];
union:=x;
end;
procedure delete(v:longint);
var    temp:longint;
begin
if find(v)
    then if t[root]>1
        then begin
        dec(t[root]);
        dec(s[root]);
        end
        else begin
        temp:=union(l[root],r[root]);
        disnode(root);
        root:=temp;
        end;
end;

//Rank Select
function rank(v:longint):longint;
var    i,j:longint;
begin
i:=root; j:=0;
while i<>0 do
    if v<=n[i]
        then i:=l[i]
        else begin
        j:=j+s[l[i]]+t[i];
        i:=r[i];
        end;
rank:=j+1;
end;
function select(k:longint):longint;
var    i:longint;
begin
if k>s[root]
    then exit(-1);
i:=root;
while true do
    begin
    if (s[l[i]]<k)and(k<=s[l[i]]+t[i])
        then exit(n[i]);
    if k<=s[l[i]]
        then i:=l[i]
        else begin
        k:=k-s[l[i]]-t[i];
        i:=r[i];
        end;
    end;
end;

//Pred Succ
function pred(v:longint):longint;
var    flag:boolean;
begin
flag:=not find(v);
if flag then insert(v);
if l[root]=0
    then pred:=v
    else pred:=max(l[root]);
if flag then delete(v);
end;
function succ(v:longint):longint;
var    flag:boolean;
begin
flag:=not find(v);
if flag then insert(v);
if r[root]=0
    then succ:=v
    else succ:=min(r[root]);
if flag then delete(v);
end;

//Main
begin
assign(input,'bst.in'); reset(input);
assign(output,'bst1.out'); rewrite(output);
readln(q);
s[0]:=0; t[0]:=0;
tt:=0; root:=0; top:=0;
for i:=1 to q do
    begin
    readln(c,x);
    case c of
        1:insert(x);
        2:delete(x);
        3:writeln(find(x));
        4:writeln(rank(x));
        5:writeln(select(x));
        6:writeln(pred(x));
        7:writeln(succ(x));
        end;
    end;
close(input); close(output);
end.

我在这里用了栈优化了新建和删除节点

将删除的节点压进一个栈新建节点时优先从栈中取节点栈空再新建

这样2000000的数据只需要300000的数组(其实可以更少)

不过如果2000000的插入就惨了这里的优化是针对随机数据的

真正爆了也是RP问题

真正数据出到数组开不下只能用栈优化一下否则用就指针(调试得吐血)

我从一篇论文里才知道 Noi2005的Sequence是需要用栈优化的

否则会MLE的很惨 (据说不优化会用到100MB的内存)

如过碰到子树的删除可以将删除的子树根节点压入栈

新建节点取用时先把节点弹出如果所取节点有儿子就把再儿子压栈

这样免去了遍历子树也可以算是lazy思想的小小应用

对于树这种递归结构通常用栈可以解决很多问题

(栈果然和递归有着可怕的联系)

下面是splay tree的重头戏

也就是伸展树的灵魂——splay操作牛B的地方

我们先看splay是如何解决区间问题的

区间问题的操作无非是如下几个

　　区间查询(最值求和...)

　　区间修改(统一加一个数统一乘一个数...)

　　区间插入(插入一段或一个值)

　　区间删除(删除一段或一个值)

　　区间交换

前2种操作线段树可以很好的处理

后3种就是要用伸展树解决的了

如果splay树的中序遍历是原序列

对于区间[x,y]我们先把x-1旋转到根

再把y+1转到根的右子节点

(当然这里的x和y是节点的rank值 而不是节点内存的n值

也就是节点在原序列的位置)

我们可以看到这时根节点的右子节点的左子树就是[x,y]内所有的数了

于是区间操作就变得可行了只要对这棵左子树下手就行了

我们结合pku3468来讨论一下

原题

　　http://acm.pku.edu.cn/JudgeOnline/problem?id=3468

题意

　　正如题目相当simple 很裸

　　维护一个数列支持区间统一加一个数和查询区间和

用线段树解决很简单

运用一下lazy思想给所要修改的区间打一个标记

然后查询到时将标记下传得到所查区间的值

代码贴一下

 1 const    maxn=200000;
 2  var    l,r,ls,rs:array[1..maxn shl 1]of longint;
 3     v,s:array[1..maxn shl 1]of int64;
 4     m:array[1..maxn]of longint;
 5     n,tt,i,q,a,b,c:longint;
 6     ch,blank:char;
 7  procedure build(a,b:longint);
 8  var    x,mid:longint;
 9  begin
10 inc(tt); x:=tt;
11 l[x]:=a; r[x]:=b;
12 v[x]:=0;
13  if b-a=1
14     then begin
15     s[x]:=m[b];
16     exit; end
17     else begin
18     mid:=(a+b)shr 1;
19     ls[x]:=tt+1; build(a,mid);
20     rs[x]:=tt+1; build(mid,b);
21     s[x]:=s[ls[x]]+s[rs[x]];
22     end;
23  end;
24  procedure clean(x:longint);
25  begin
26 if v[x]<>0
27     then begin
28     s[x]:=s[x]+(r[x]-l[x])*v[x];
29             if ls[x]<>0 then v[ls[x]]:=v[ls[x]]+v[x];
30     if rs[x]<>0 then v[rs[x]]:=v[rs[x]]+v[x];
31     v[x]:=0;
32     end;
33 end;
34 procedure insert(x,a,b,c:longint);
35 var    mid:longint;
36 begin
37 clean(x);
38 if (a<=l[x])and(r[x]<=b)
39     then begin
40     v[x]:=v[x]+c;
41     exit;
42     end;
43 mid:=(l[x]+r[x])shr 1;
44 if a<mid then insert(ls[x],a,b,c);
45 if mid<b then insert(rs[x],a,b,c);
46 clean(ls[x]); clean(rs[x]);
47 s[x]:=s[ls[x]]+s[rs[x]];
48 end;
49 function query(x,a,b:longint):int64;
50 var    mid:longint;
51     ans:int64;
52 begin
53 clean(x);
54 if (a<=l[x])and(r[x]<=b)
55     then begin
56     query:=s[x];
57     exit;
58     end;
59 ans:=0;
60 mid:=(l[x]+r[x])shr 1;
61 if a<mid then ans:=ans+query(ls[x],a,b);
62 if mid<b then ans:=ans+query(rs[x],a,b);
63 clean(ls[x]); clean(rs[x]);
64 s[x]:=s[ls[x]]+s[rs[x]];
65 query:=ans;
66 end;
67 begin
68 assign(input,'simple.in'); reset(input);
69 assign(output,'simple.out'); rewrite(output);
70 readln(n,q);
71 for i:=1 to n do
72     read(m[i]);
73 tt:=0;
74 build(0,n);
75 readln;
76 for i:=1 to q do
77     begin
78     read(ch); read(blank);
79     case ch of
80         'Q':    begin
81             readln(a,b);
82             writeln(query(1,a-1,b));
83             end;
84         'C':    begin
85             readln(a,b,c);
86             insert(1,a-1,b,c);
87             end;
88         end;
89     end;
90 close(input); close(output);
91 end.
92

顺便给一个加强版支持区间乘一个数

  1 const    maxn=100000;
  2 var    l,r,ls,rs:array[1..maxn shl 1-1]of longint;
  3     u,v,s:array[1..maxn shl 1-1]of int64;
  4             m:array[1..maxn]of longint;
  5             n,q,tt,i,a,b,c:longint;
  6     ch,blank:char;
  7 procedure build(a,b:longint);
  8 var    mid,x:longint;
  9 begin
 10 inc(tt); x:=tt;
 11 l[x]:=a; r[x]:=b;
 12 u[x]:=0; v[x]:=1;
 13 if b-a=1
 14     then s[x]:=m[b]
 15     else begin
 16     mid:=(a+b)shr 1;
 17     ls[x]:=tt+1; build(a,mid);
 18     rs[x]:=tt+1; build(mid,b);
 19     s[x]:=s[ls[x]]+s[rs[x]];
 20     end;
 21 end;
 22 procedure clean(x:longint);
 23 begin
 24 if (u[x]<>0)or(v[x]<>1)
 25     then begin
 26     s[x]:=s[x]*v[x]+u[x]*(r[x]-l[x]);
 27     if ls[x]<>0
 28         then begin
 29         v[ls[x]]:=v[ls[x]]*v[x];
 30         u[ls[x]]:=u[ls[x]]*v[x]+u[x];
 31         end;
 32     if rs[x]<>0
 33         then begin
 34         v[rs[x]]:=v[rs[x]]*v[x];
 35         u[rs[x]]:=u[rs[x]]*v[x]+u[x];
 36         end;
 37     v[x]:=1; u[x]:=0;
 38     end;
 39 end;
 40 procedure mult(x,a,b,c:longint);
 41 var    mid:longint;
 42 begin
 43 clean(x);
 44 if (a<=l[x])and(r[x]<=b)
 45     then begin
 46     u[x]:=u[x]*c;
 47     v[x]:=v[x]*c;
 48     exit; end;
 49 mid:=(l[x]+r[x])shr 1;
 50 if a<mid then mult(ls[x],a,b,c);
 51 if mid<b then mult(rs[x],a,b,c);
 52 clean(ls[x]); clean(rs[x]);
 53 s[x]:=s[ls[x]]+s[rs[x]];
 54 end;
 55 procedure plus(x,a,b,c:longint);
 56 var    mid:longint;
 57 begin
 58 clean(x);
 59 if (a<=l[x])and(r[x]<=b)
 60     then begin
 61     u[x]:=u[x]+c;
 62     exit; end;
 63 mid:=(l[x]+r[x])shr 1;
 64 if a<mid then plus(ls[x],a,b,c);
 65 if mid<b then plus(rs[x],a,b,c);
 66 clean(ls[x]); clean(rs[x]);
 67 s[x]:=s[ls[x]]+s[rs[x]];
 68 end;
 69 function query(x,a,b:longint):int64;
 70 var    mid:longint;
 71     ans:int64;
 72 begin
 73 clean(x);
 74 if (a<=l[x])and(r[x]<=b)
 75     then begin
 76     query:=s[x];
 77     exit; end;
 78 ans:=0;
 79 mid:=(l[x]+r[x])shr 1;
 80 if a<mid then ans:=ans+query(ls[x],a,b);
 81 if mid<b then ans:=ans+query(rs[x],a,b);
 82 query:=ans;
 83 clean(ls[x]); clean(rs[x]);
 84 s[x]:=s[ls[x]]+s[rs[x]];
 85 end;
 86 begin
 87 assign(input,'ssimple.in'); reset(input);
 88 assign(output,'ssimple.out'); rewrite(output);
 89 readln(n,q);
 90 for i:=1 to n do
 91     read(m[i]);
 92 readln;
 93 tt:=0;
 94 build(0,n);
 95 for i:=1 to q do
 96     begin
 97     read(ch); read(blank);
 98     case ch of
 99         'Q':    begin
100             readln(a,b);
101             writeln(query(1,a-1,b));
102             end;
103         'M':    begin
104             readln(a,b,c);
105             mult(1,a-1,b,c);
106             end;
107         'P':    begin
108             readln(a,b,c);
109             plus(1,a-1,b,c);
110             end;
111         end;
112     end;
113 close(input); close(output);
114 end.
115

那么用splay来解决怎么做呢

我们给每个节点记录一下sum值和n值 sum值就是子树的和

还要给一个标记域以便运用lazy思想标记域存个delta表示子树的值都得加delta

旋转的时候维护好sum和size就行了

这样splay操作就不仅是提根也顺便维护了路径上的所有节点

对于区间[x,y]修改查询rank为x-1和y+1的节点也就是select操作

然后我们把x-1旋转到根再把y+1转到根的右子节点

我们就得到根右子节点的左子树是区间[x,y]

运用lazy思想给这个子树的根节点左右打个标记即可

然后更新一下根节点的值继续向上更新父亲和祖父节点

也就是更新根节点和根节点的右子节点

对于区间查询也是如此

利用splay得到一棵能代表区间的子树

查询子树的根节点就是答案

贴个代码

  1 const    max=200000;
  2     maxn=120000;
  3 var    l,r,f:array[0..max]of longint;
  4     s,d,sum,n:array[0..max]of int64;
  5     dat:array[1..maxn]of longint;
  6     stack:array[1..max]of longint;
  7     m,q,tt,root,i,a,b,c,top:longint;
  8     ch,blank:char;
  9 procedure down(x:longint);
 10 begin
 11 if x=0 then exit;
 12 if l[x]<>0 then d[l[x]]:=d[l[x]]+d[x];
 13 if r[x]<>0 then d[r[x]]:=d[r[x]]+d[x];
 14 sum[x]:=sum[x]+d[x]*s[x];
 15 n[x]:=n[x]+d[x];
 16 d[x]:=0;
 17 end;
 18 procedure zig(var x:longint);
 19 var    y:longint;
 20 begin
 21 down(x); down(l[x]);
 22 y:=l[x]; l[x]:=r[y]; r[y]:=x;
 23 f[y]:=f[x]; f[x]:=y;
 24 if l[x]<>0 then f[l[x]]:=x;
 25 s[y]:=s[x]; s[x]:=s[l[x]]+s[r[x]]+1;
 26 down(r[x]); down(l[x]);
 27 sum[y]:=sum[x]; sum[x]:=sum[l[x]]+sum[r[x]]+n[x];
 28 x:=y;
 29 end;
 30 procedure zag(var x:longint);
 31 var    y:longint;
 32 begin
 33 down(x); down(r[x]);
 34 y:=r[x]; r[x]:=l[y]; l[y]:=x;
 35 f[y]:=f[x]; f[x]:=y;
 36 if r[x]<>0 then f[r[x]]:=x;
 37 s[y]:=s[x]; s[x]:=s[l[x]]+s[r[x]]+1;
 38 down(r[x]); down(l[x]);
 39 sum[y]:=sum[x]; sum[x]:=sum[l[x]]+sum[r[x]]+n[x];
 40 x:=y;
 41 end;
 42 procedure splay(x:longint; var S:longint);
 43 begin
 44 while f[x]<>f[S] do
 45     if l[f[x]]=x
 46         then begin
 47         if f[x]=S
 48             then zig(S)
 49             else if l[f[f[x]]]=f[x]
 50                 then zig(l[f[f[x]]])
 51                 else zig(r[f[f[x]]]);
 52         end
 53         else begin
 54         if f[x]=S
 55             then zag(S)
 56             else if l[f[f[x]]]=f[x]
 57                 then zag(l[f[f[x]]])
 58                 else zag(r[f[f[x]]]);
 59         end;
 60 end;
 61 procedure newnode(var x:longint);
 62 begin
 63 if top>0
 64     then begin x:=stack[top]; dec(top); end
 65     else begin inc(tt); x:=tt; end;
 66 l[x]:=0; r[x]:=0; f[x]:=0;
 67 end;
 68 procedure recnode(var x:longint);
 69 begin
 70 inc(top); stack[top]:=x;
 71 end;
 72 procedure build(var x:longint; a,b:longint);
 73 var    mid:longint;
 74 begin
 75 if a>b then exit;
 76 newnode(x);
 77 mid:=(a+b)shr 1; n[x]:=dat[mid];
 78 build(l[x],a,mid-1); build(r[x],mid+1,b);
 79 if l[x]<>0 then f[l[x]]:=x;
 80 if r[x]<>0 then f[r[x]]:=x;
 81 sum[x]:=sum[l[x]]+sum[r[x]]+n[x];
 82 s[x]:=s[l[x]]+s[r[x]]+1;
 83 end;
 84 function select(x,k:longint):longint;
 85 begin
 86 if s[l[x]]+1=k then exit(x);
 87 if k<=s[l[x]] then select:=select(l[x],k)
 88     else select:=select(r[x],k-s[l[x]]-1);
 89 end;
 90 procedure plus(a,b,c:longint);
 91 var    x,y:longint;
 92 begin
 93 x:=select(root,a-1);
 94 y:=select(root,b+1);
 95 splay(x,root);
 96 splay(y,r[root]);
 97 y:=l[r[root]];
 98 d[y]:=d[y]+c;
 99 splay(y,root);
100 end;
101 function getsum(a,b:longint):int64;
102 var    x,y:longint;
103 begin
104 x:=select(root,a-1);
105 y:=select(root,b+1);
106 splay(x,root);
107 splay(y,r[root]);
108 y:=l[r[root]];
109 down(y);
110 getsum:=sum[y];
111 splay(y,root);
112 end;
113 begin
114 assign(input,'simple.in'); reset(input);
115 assign(output,'simple0.out'); rewrite(output);
116 readln(m,q);
117 dat[1]:=0; dat[m+2]:=0;
118 for i:=2 to m+1 do
119     read(dat[i]);
120 readln;
121 s[0]:=0; tt:=0; root:=0;
122 build(root,1,m+2);
123 for i:=1 to q do
124     begin
125     read(ch); read(blank);
126     case ch of
127         'C':
128             begin
129             readln(a,b,c);
130             plus(a+1,b+1,c);
131             end;
132         'Q':
133             begin
134             readln(a,b);
135             writeln(getsum(a+1,b+1));
136             end;
137         end;
138     end;
139 close(input);
140 close(output);
141 end.
142

具体测试中splay比线段树慢很多也不是很好写

那我们为什么还要用splay呢

因为线段树有缺陷线段树受不了插入和删除

我们再讨论一下pku3580 supermemo

(Noi那一个维护数列的题目难度和这个差不多 <NOI2005 维护数列>

内容也差不多就不细写了注意上文提到的内存问题即可)

原题

　　http://acm.pku.edu.cn/JudgeOnline/problem?id=3580

题意

　　还是很裸不过配的上super这个词

ADD x y D: Add D to each number in sub-sequence {A_x ... A_y}. For example, performing "ADD 2 4 1" on {1, 2, 3, 4, 5} results in {1, 3, 4, 5, 5}
REVERSE x y: reverse the sub-sequence {A_x ... A_y}. For example, performing "REVERSE 2 4" on {1, 2, 3, 4, 5} results in {1, 4, 3, 2, 5}
REVOLVE x y T: rotate sub-sequence {A_x ... A_y} T times. For example, performing "REVOLVE 2 4 2" on {1, 2, 3, 4, 5} results in {1, 3, 4, 2, 5}
INSERT x P: insert P after A_x. For example, performing "INSERT 2 4" on {1, 2, 3, 4, 5} results in {1, 2, 4, 3, 4, 5}
DELETE x: delete A_x. For example, performing "DELETE 2" on {1, 2, 3, 4, 5} results in {1, 3, 4, 5}
MIN x y: query the participant what is the minimum number in sub-sequence {A_x ... A_y}. For example, the correct answer to "MIN 2 4" on {1, 2, 3, 4, 5} is 2

　　英文很好懂的不翻译了

说来很惭愧调了2天才AC 唉不堪回首

　　add已经在上面讨论过了

　　reverse也是用的lazy标记的方法记录一个布尔变量表示当前子树需不需要交换左右儿子(下传时是用not运算而不是直接赋值)

　　min操作要求我们维护一个min域 (注意在add的时候直接加min 千万不要从儿子处更新)

　　insert 先把x转到根再把x+1转到右子节点给右子节点的左儿子挂个新节点(注意要向上更新)

　　delete 先把x转到根再把x+2转到右子节点砍了右子节点的左儿子(注意要向上更新)

　　revolve本质是交换区间我们先把2个区间分离到出来然后经过一系列的指针操作解决(相当繁琐注意细节给个图好看着写代码)

　　假设交换区间[a,b][b+1,c] 如图所示

　　 -->-->
-->

最后贴一下我的代码

  1 const    maxn=200000;
  2     inf=maxlongint shr 1;
  3 var    l,r,s,f,dat:array[0..maxn]of longint;
  4     n,d,min:array[0..maxn]of int64;
  5     w:array[0..maxn]of boolean;
  6     i,g,x,y,k,m,q,delta,root,tt,temp:longint;
  7     st:string;
  8     ch:char;
  9 procedure down(x:longint);
 10 var     temp:longint;
 11 begin
 12 if d[x]<>0
 13     then begin
 14     if l[x]<>0 then d[l[x]]:=d[l[x]]+d[x];
 15     if r[x]<>0 then d[r[x]]:=d[r[x]]+d[x];
 16     n[x]:=n[x]+d[x]; min[x]:=min[x]+d[x];
 17     d[x]:=0;
 18     end;
 19 if w[x]
 20     then begin
 21     if l[x]<>0 then w[l[x]]:=not w[l[x]];
 22     if r[x]<>0 then w[r[x]]:=not w[r[x]];
 23     temp:=l[x]; l[x]:=r[x]; r[x]:=temp;
 24     w[x]:=false;
 25     end;
 26 end;
 27 procedure out(x:longint);
 28 begin
 29 if x=0 then exit;
 30 down(x);
 31 out(l[x]);
 32 if n[x]<>inf then write(n[x],' ');
 33 out(r[x]);
 34 end;
 35 procedure update(x:longint);
 36 begin
 37 if x=0 then exit;
 38 down(l[x]); down(r[x]);
 39 s[x]:=s[l[x]]+s[r[x]]+1;
 40 if min[l[x]]<min[r[x]]
 41     then min[x]:=min[l[x]]
 42     else min[x]:=min[r[x]];
 43 if n[x]<min[x] then min[x]:=n[x];
 44 end;
 45 procedure zig(var x:longint);
 46 var    y:longint;
 47 begin
 48 y:=l[x]; l[x]:=r[y]; r[y]:=x;
 49 f[y]:=f[x]; f[x]:=y; if l[x]<>0 then f[l[x]]:=x;
 50 update(x); update(y); x:=y;
 51 end;
 52 procedure zag(var x:longint);
 53 var    y:longint;
 54 begin
 55 y:=r[x]; r[x]:=l[y]; l[y]:=x;
 56 f[y]:=f[x]; f[x]:=y; if r[x]<>0 then f[r[x]]:=x;
 57 update(x); update(y); x:=y;
 58 end;
 59 procedure splay(x:longint; var O:longint);
 60 begin
 61 while f[x]<>f[O] do
 62     if l[f[x]]=x
 63         then begin
 64         if f[x]=O
 65             then zig(O)
 66             else if l[f[f[x]]]=f[x]
 67                 then zig(l[f[f[x]]])
 68                 else zig(r[f[f[x]]]);
 69         end
 70         else begin
 71         if f[x]=O
 72             then zag(O)
 73             else if l[f[f[x]]]=f[x]
 74                 then zag(l[f[f[x]]])
 75                 else zag(r[f[f[x]]]);
 76         end;
 77 end;
 78 procedure build(var x:longint; a,b:longint);
 79 var    mid:longint;
 80 begin
 81 if a>b then exit;
 82 inc(tt); x:=tt;
 83 mid:=(a+b)shr 1; n[x]:=dat[mid];
 84 build(l[x],a,mid-1); build(r[x],mid+1,b);
 85 if l[x]<>0 then f[l[x]]:=x;
 86 if r[x]<>0 then f[r[x]]:=x;
 87 update(x);
 88 end;
 89 function select(x,k:longint):longint;
 90 begin
 91 down(x);
 92 if s[l[x]]+1=k then exit(x);
 93 if k<=s[l[x]] then select:=select(l[x],k)
 94     else select:=select(r[x],k-s[l[x]]-1);
 95 end;
 96 begin
 97 assign(input,'memo.in'); reset(input);
 98 assign(output,'memo.out'); rewrite(output);
 99 readln(m);
100 dat[1]:=inf; dat[m+2]:=inf;
101 for i:=2 to m+1 do
102     readln(dat[i]);
103 root:=0; tt:=0; min[0]:=inf; s[0]:=0;
104 build(root,1,m+2);
105 readln(q);
106 //out(root); writeln;
107 for g:=1 to q do
108     begin
109     ch:='^'; st:='';
110     while ch<>' ' do
111         begin
112         st:=st+ch;
113         read(ch);
114         end;
115     if st='^ADD'
116         then begin
117         readln(x,y,delta); inc(x); inc(y);
118         x:=select(root,x-1); y:=select(root,y+1);
119         splay(x,root); splay(y,r[root]);
120         x:=l[r[root]];
121         d[x]:=d[x]+delta; down(x);
122         update(r[root]); update(root);
123         end;
124     if st='^INSERT'
125         then begin
126         readln(x,delta); inc(x);
127         y:=select(root,x+1);
128         x:=select(root,x);
129         splay(x,root); splay(y,r[root]);
130         inc(tt); l[r[root]]:=tt; x:=l[r[root]];
131         n[x]:=delta; min[x]:=n[x]; s[x]:=1; f[x]:=r[root];
132         update(r[root]); update(root);
133         end;
134     if st='^DELETE'
135         then begin
136         readln(x); inc(x);
137         y:=select(root,x+1); x:=select(root,x-1);
138         splay(x,root); splay(y,r[root]);
139         l[r[root]]:=0;
140         update(r[root]); update(root);
141         end;
142     if st='^REVERSE'
143         then begin
144         readln(x,y); inc(x); inc(y);
145         x:=select(root,x-1); y:=select(root,y+1);
146         splay(x,root); splay(y,r[root]);
147         x:=l[r[root]];
148         w[x]:=not w[x]; down(x);
149         update(r[root]); update(root);
150         end;
151     if st='^REVOLVE'
152         then begin
153         readln(x,y,k); inc(x); inc(y);
154         if x=y then begin {out(root);writeln;} continue; end;
155         k:=k mod (y-x+1);
156         if k=0 then begin {out(root);writeln;} continue; end;
157         k:=select(root,y-k); x:=select(root,x-1); y:=select(root,y+1);
158         splay(k,root); splay(x,l[root]); splay(y,r[root]);
159         x:=r[l[root]]; y:=l[r[root]];
160         r[l[root]]:=0; l[r[root]]:=0;
161         f[x]:=0; f[y]:=0;
162         r[l[root]]:=y; if y<>0 then f[y]:=l[root];
163         update(l[root]);
164         y:=l[root]; l[root]:=x; if x<>0 then f[x]:=root;
165         update(r[root]); update(l[root]); update(root);
166         x:=select(root,1);
167         splay(x,root);
168         l[root]:=y; f[y]:=root;
169         update(root);
170         end;
171     if st='^MIN'
172         then begin
173         readln(x,y); inc(x); inc(y);
174         x:=select(root,x-1);
175         y:=select(root,y+1);
176         splay(x,root); splay(y,r[root]);
177         x:=l[r[root]];
178         down(x); writeln(min[x]);
179         continue;
180         end;
181     //out(root);writeln;
182     end;
183 close(input); close(output);
184 end.
185

【上篇】dancing links详解 dancing links详解
【下篇】静态循环队列的相关操作及详解静态循环队列的相关操作及详解

作者: ominous

该日志由 ominous 于7年前发表在综合分类下，最后更新于 2017年11月03日.
转载请注明: equance]伸展树Splay & 平衡树SBT(下) | 学步园 +复制链接

抱歉!评论已关闭.

学步园