注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Tyvj】【咱只是用来做模板】【普通平衡树】  

2014-03-19 16:06:46|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   = =论3.18被题虐,写树的点分治O(nlog^2n)又丧(Xi)心(Wen)病(Le)狂(Jian)地被卡了。感动涕零,截图纪念。【BZOJ1058】【ZJOI2007】【报表统计】 - z55250825 - z55250825
    【BZOJ1058】【ZJOI2007】【报表统计】 - z55250825 - z55250825
    因为本蒟蒻一旦碰上测验啥的看到题一想出个好(Bao)点(Li)的解法 码代码的时候手易抖...然后经常平衡树被华丽的写挂写卡,再加上咱的Splay的巨囧无比的常数...所以碰到普通的用BST的题目准备写treap(话说随机数什么的直接用系统的会不会很危险...),然后发现....咱只会把一堆点splay到根之后再搞其他操作....对treap非常不适应....然后开始搞一些模板题...
     treap的插入删除都还可以,一个while即可解决,写的是自顶向下查找的,注意如果有size域还要在查找的过程中维护一下size即可。然后如果是根删除的话第一次旋转的时候把根更新为父亲即可。
     然后是查找第k大,用size即可。查找某个元素,也是普通的平衡树即可。修改的话插入删除即可。前驱后继啥的直接两个查询即可,都是while直接搞就可以了。查找某个元素的排名,实际上就是查找多少个数比它小,查找的时候弄一下size即可。然后喜闻乐见的没了。
     另外这题对于相同的数可以缩在一起,增加一个域记录这个数有多少个,然后计算size的时候考虑一下这个即可,这样子常数小一点。然后假如只maintain size域的话,rotate直接暴力两行也许更快.....
      ps:后面两个文艺和二逼= =咱不会treap写= =,文艺参考hdu 的play with chain貌似就可以了,二逼区间K大可以离散化然后线段树套权值线段树做,也可以直接做...反正都用不上treap。
=====【普通平衡树P】=====================================

program tyvj;
const maxn=100010;
type node=record
     son:array[0..1]of longint;
     f,size,ran,a:longint;
     end;

var t:array[0..maxn]of node;
    root,n,tot:longint;

procedure rotate(p:longint);
var y,w,ww:longint;
begin
  with t[p] do
   begin
     y:=f;w:=ord(t[y].son[1]=p);
     ww:=ord(t[t[y].f].son[1]=y);
     f:=t[y].f;
     t[t[y].f].son[ww]:=p;
     t[son[w xor 1]].f:=y;
     t[y].son[w]:=son[w xor 1];
     t[y].f:=p;
     son[w xor 1]:=y;
     t[y].size:=t[t[y].son[0]].size+t[t[y].son[1]].size+1;
     size:=t[son[0]].size+t[son[1]].size+1;
   end;
end;

function new(c,fa:longint):longint;
var p:longint;
begin
  inc(tot);p:=tot;
  t[p].a:=c;
  t[p].ran:=random(5000000);
  t[p].size:=1;
  t[p].f:=fa;
  t[p].son[0]:=0;
  t[p].son[1]:=0;
  exit(p);
end;

procedure insert(c:longint);
var p:longint;
begin
  p:=root;
  if root=0 then
   begin
     root:=new(c,0);
     exit;
   end;
  while (t[p].son[ord(t[p].a<c)]<>0) do
    begin
      inc(t[p].size);
      p:=t[p].son[ord(t[p].a<c)];
    end;
  inc(t[p].size);
  t[p].son[ord(t[p].a<c)]:=new(c,p);
  while (t[tot].f<>0)and(t[tot].ran>t[t[tot].f].ran) do rotate(tot);
  if (t[tot].f=0) then root:=tot;
end;

procedure delete(c:longint);
var p:longint;
begin
  p:=root;
  while (t[p].a<>c) do
   begin
     dec(t[p].size);
     p:=t[p].son[ord(t[p].a<c)];
   end;
  while (t[p].son[0]<>0)or(t[p].son[1]<>0) do
   begin
     if t[t[p].son[0]].ran>t[t[p].son[1]].ran then rotate(t[p].son[0])
                                              else rotate(t[p].son[1]);
     dec(t[t[p].f].size);
     if root=p then root:=t[p].f;
   end;
  t[t[p].f].son[ord(t[t[p].f].son[1]=p)]:=0;
end;

function rank(x:longint):longint;
var p,ans:longint;
begin
  p:=root;
  ans:=1;
  while p<>0 do
   begin
     if t[p].a<x then
      begin
        ans:=ans+t[t[p].son[0]].size+1;
        p:=t[p].son[1];
      end
     else p:=t[p].son[0];
   end;
  exit(ans);
end;

function kth(x:longint):longint;
var p:longint;
begin
  p:=root;
  while p<>0 do
   begin
     if (t[t[p].son[0]].size+1=x) then exit(t[p].a);
     if (t[t[p].son[0]].size+1>x) then p:=t[p].son[0]
     else begin
       dec(x,t[t[p].son[0]].size+1);
       p:=t[p].son[1];
     end;
   end;
end;

function pre(x:longint):longint;
var p,ans:longint;
begin
  p:=root;
  while p<>0 do
   begin
     if (t[p].a>=x)then p:=t[p].son[0]
     else begin
     ans:=t[p].a;
     p:=t[p].son[1];
     end;
   end;
  exit(ans);
end;

function succ(x:longint):longint;
var p,ans:longint;
begin
  p:=root;
  while p<>0 do
   begin
     if (t[p].a<=x)then p:=t[p].son[1]
     else begin
     ans:=t[p].a;
     p:=t[p].son[0];
     end;
   end;
  exit(ans);
end;

procedure init;
var i,u,v:longint;
begin
  read(n);
  for i:=1 to n do
   begin
     read(u,v);
     case u of
      1:insert(v);
      2:delete(v);
      3:writeln(rank(v));
      4:writeln(kth(v));
      5:writeln(pre(v));
      6:writeln(succ(v));
     end;
   end;
end;

begin
randomize;
  init;
end.

=====【普通平衡树C++】(其实就是翻译...)(但是貌似比P快了70ms...)======

#include <cstdio>
#include <cstdlib>
#include <cstring>
#define maxn 100010
using namespace std;

struct node{
int son[2],f,size,a,ran;
}t[maxn];

int n,tot,root;

void rotate(int p)
{
int y=t[p].f,w=t[y].son[1]==p,ww=t[t[y].f].son[1]==y;
t[t[p].son[w^1]].f=y;
t[y].son[w]=t[p].son[w^1];
t[p].f=t[y].f;
t[t[y].f].son[ww]=p;
t[y].f=p;
t[p].son[w^1]=y;
t[y].size=t[t[y].son[0]].size+t[t[y].son[1]].size+1;
t[p].size=t[t[p].son[0]].size+t[t[p].son[1]].size+1;
}

int neww(int c,int fa)
{
int p=++tot;
t[p].a=c;
t[p].ran=rand();
t[p].size=1;
t[p].son[0]=t[p].son[1]=0;
t[p].f=fa;
return p;
}

void insert(int c)
{
int p=root;
if (!p) {root=neww(c,0);return;}
while (t[p].son[t[p].a<c]) t[p].size++,p=t[p].son[t[p].a<c];
t[p].size++;
t[p].son[t[p].a<c]=neww(c,p);
while (t[tot].f&&t[tot].ran>t[t[tot].f].ran) rotate(tot);
if (!t[tot].f) root=tot;
}

void deletee(int c)
{
int p=root;
while (t[p].a!=c)
{
t[p].size--;
p=t[p].son[t[p].a<c];
}
while (t[p].son[0]||t[p].son[1])
{
if (t[t[p].son[0]].ran>t[t[p].son[1]].ran) rotate(t[p].son[0]);
else rotate(t[p].son[1]);
if (p==root) root=t[p].f;
t[t[p].f].size--;
}
t[t[p].f].son[t[t[p].f].son[1]==p]=0;
}

int rank(int kth)
{
int p=root;
while (p)
{
if (t[t[p].son[0]].size+1==kth) {return t[p].a;}
if (t[t[p].son[0]].size+1>kth) p=t[p].son[0];
else kth-=t[t[p].son[0]].size+1,p=t[p].son[1];
}
}

int pre(int c)
{
int p=root,ans=-1;
while (p)
{
if (t[p].a<c) ans=t[p].a,p=t[p].son[1];
else p=t[p].son[0];
}
return ans;
}

int succ(int c)
{
int p=root,ans=-1;
while (p)
{
if (t[p].a<=c) p=t[p].son[1];
else ans=t[p].a,p=t[p].son[0];
}
return ans;
}

int kth(int c)
{
int p=root,ans=1;
while (p)
{
if (t[p].a<c) ans+=t[t[p].son[0]].size+1,p=t[p].son[1];
else p=t[p].son[0];
}
return ans;
}

void init()
{
root=tot=t[0].size=0;
t[0].ran=-1<<20;
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
int num,x;
scanf("%d%d",&num,&x);
if (num==1) insert(x);
if (num==2) deletee(x);
if (num==3) printf("%d\n",kth(x));
if (num==4) printf("%d\n",rank(x));
if (num==5) printf("%d\n",pre(x));
if (num==6) printf("%d\n",succ(x));
}
}

int main()
{
srand(0);
init();
return 0;
}



  评论这张
 
阅读(41)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017