二次联通门 : codevs 4244 平衡树练习

Splay实测指针占用空间大约是数组的3倍, 且时间上也慢了差不多1s

数组版评测记录如下

指针版评测记录如下

    以上数据仅限这一个题, 对于别的题,指针其实是比数组快的

  虽然这样。。。

  但是指针写起来就是看着顺眼。。。。

/*
指针版 */
#include <cstdio>
#include <cstdlib> void read (int &now)
{
now = ;
register char word = getchar ();
bool temp = false;
while (word < '' || word > '')
{
if (word == '-')
temp = true;
word = getchar ();
}
while (word >= '' && word <= '')
{
now = now * + word - '';
word = getchar ();
}
if (temp)
now = -now;
} struct Splay_Tree_Data
{
Splay_Tree_Data *child[]; Splay_Tree_Data *father; int size, weigth; int key;
inline void Updata ()
{
this->size = this->weigth;
if (this->child[] != NULL)
this->size += this->child[]->size;
if (this->child[] != NULL)
this->size += this->child[]->size;
} inline int Get_Pos ()
{
return this->father->child[] == this;
} Splay_Tree_Data ()
{
child[] = NULL;
child[] = NULL;
size = weigth = ;
father = NULL;
key = ;
}
}; Splay_Tree_Data *Root; class Splay_Tree_Type
{
private : inline void Rotate (Splay_Tree_Data *now)
{
Splay_Tree_Data *Father = now->father;
if (now == NULL || Father == NULL)
return ;
int pos = now->Get_Pos () ^ ;
Father->child[pos ^ ] = now->child[pos];
if (now->child[pos])
now->child[pos]->father = Father;
if ((now->father = Father->father) != NULL)
now->father->child[now->father->child[] == Father] = now;
Father->father = now;
now->child[pos] = Father;
Father->Updata ();
now->Updata ();
if (now->father == NULL)
Root = now;
} inline void Splay (Splay_Tree_Data *now, Splay_Tree_Data *to = NULL)
{
for (; now->father != to; Rotate (now))
if (now->father->father != to)
Rotate (now->Get_Pos () == now->father->Get_Pos () ? now->father : now);
} public : void Insert (int x)
{
Splay_Tree_Data *now = Root;
if (Root == NULL)
{
Root = new Splay_Tree_Data;
Root->key = x;
Root->father = NULL;
return ;
}
int pos;
while (true)
{
if (now->key == x)
{
now->size ++;
now->weigth ++;
Splay (now);
return ;
}
pos = x > now->key ? : ;
if (now->child[pos] == NULL)
{
now->child[pos] = new Splay_Tree_Data;
now->child[pos]->father = now;
now->child[pos]->key = x;
Splay (now->child[pos]);
return ;
}
now = now->child[pos];
}
} bool Find (int x)
{
Splay_Tree_Data *now = Root;
while (true)
{
if (x == now->key)
return true;
else if (x < now->key && now->child[] != NULL)
now = now->child[];
else if (x > now->key && now->child[] != NULL)
now = now->child[];
else
return false;
}
}
}; Splay_Tree_Type Tree; int N, M; int main (int argc, char *argv[])
{
int x;
for (read (N), read (M); N--; )
{
read (x);
Tree.Insert (x);
}
for (; M--; )
{
read (x);
if (Tree.Find (x))
printf ("1 ");
else
printf ("0 ");
}
return ;
}
/*
数组版 */
#include <cstdio> #define Max 10000002 void read (int &now)
{
now = ;
register char word = getchar ();
bool temp = false;
while (word < '' || word > '')
{
if (word == '-')
temp = true;
word = getchar ();
}
while (word >= '' && word <= '')
{
now = now * + word - '';
word = getchar ();
}
if (temp)
now = -now;
} class Splay_Tree_Type
{
private : struct Splay_Tree_Date
{
int key;
int father;
int child[];
}
tree[Max]; int Count;
int Root; inline int Get_Son (int now)
{
return tree[tree[now].father].child[] == now;
} inline void Rotate (int now)
{
int father = tree[now].father;
int Grand = tree[father].father;
int pos = Get_Son (now);
tree[father].child[pos] = tree[now].child[pos ^ ];
tree[tree[father].child[pos]].father = father;
tree[now].child[pos ^ ] = father;
tree[father].father = now;
tree[now].father = Grand;
if (Grand)
tree[Grand].child[tree[Grand].child[] == father] = now;
} inline void Splay (int now)
{
for (int father; father = tree[now].father; Rotate (now))
if (tree[father].father)
Rotate (Get_Son (now) == Get_Son (father) ? father : now);
Root = now;
} public : void Insert (int x)
{
if (!Root)
{
Count++;
tree[Count].key = x;
Root = Count;
return ;
}
int now = Root, father = ;
while (true)
{
if (tree[now].key == x)
return ;
father = now;
now = tree[now].child[x > tree[father].key];
if (!now)
{
Count++;
tree[Count].key = x;
tree[Count].father = father;
tree[father].child[x > tree[father].key] = Count;
Splay (Count);
return ;
}
}
} int Find (int x)
{
int now = Root;
while (true)
{
if (x == tree[now].key)
return ;
if (x < tree[now].key && tree[now].child[])
now = tree[now].child[];
else if (x > tree[now].key && tree[now].child[])
now = tree[now].child[];
else
return ;
if (!now)
return ;
}
}
}; Splay_Tree_Type Make; int main (int argc, char *argv[])
{
int N, M;
read (N);
read (M);
int x;
for (; N--; )
{
read (x);
Make.Insert (x);
}
for (; M--; )
{
read (x);
printf ("%d ", Make.Find (x));
}
return ;
}

最新文章

  1. Echarts在JavaWeb中与后台的交互实现
  2. print输出格式总结
  3. 如何利用 JConsole观察分析Java程序的运行,进行排错调优
  4. openstack-glance
  5. poj[1185]炮兵阵地
  6. C#将JSON字符串对象序列化与反序列化
  7. 如何快速建立一个测试资源Web服务器及异步获取资源(Unity3D)
  8. 9. Add the Block Storage service
  9. 百度UEditor(富文本编辑器)的基础用法
  10. ubuntu12.04 mysql服务器乱码问题的解决办法
  11. js定时函数
  12. Spring使用@Scheduled定时调度
  13. SSIS - 5.优先约束
  14. 开发CMDB系统
  15. 网页定位点击事件js响应函数教程(Chrome)
  16. bodymovin实现将AE动画转换成HTML5动画
  17. matlab中的常用的函数&mdash;&mdash;在稀疏表示中学习到的
  18. English trip -- VC(情景课)9 D Reading 阅读练习
  19. UEFI是什么?与BIOS的区别在哪里?UEFI详解!
  20. Java网络编程学习A轮_07_基于Buffer的Socket编程

热门文章

  1. 细说浏览器输入URL后发生了什么
  2. jquery封装的方法
  3. 海思HI35xx平台软件开发快速入门之H264解码实例学习
  4. 谷歌chrome浏览器提示“喔唷 崩溃啦”的解决方案
  5. 解决:error LNK1169: 找到一个或多个多重定义的符号
  6. Javascript的异步与单线程
  7. Linux文件(夹)属性
  8. Python基础笔记一
  9. 读书笔记——《redis入门指南(第2版)》第七章 持久化
  10. PAT_B 20