bzoj 1588 splay模板题

时间:2023-01-21 22:43:23

用晚自习学了一下splay模板,没想象中那么难,主要是左旋和右旋可以简化到一个函数里边,减少代码长度。。。

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 33333
#define inf 0x3f3f3f3f
#define lc(x) ch[(x)][0]
#define rc(x) ch[(x)][1]
using namespace std;
int fa[maxn],ch[maxn][],root,k[maxn],ind=;
inline void rotate(int p)
{
int q=fa[p],y=fa[q],x=ch[q][]==p;
ch[q][x]=ch[p][x^];fa[ch[q][x]]=q;
ch[p][x^]=q;fa[q]=p;
fa[p]=y;
if(y)
{
if(ch[y][]==q)ch[y][]=p;
else ch[y][]=p;
}
}
inline void splay(int x)
{
for(int y;y=fa[x];rotate(x))
{
if(fa[y])
{
if(y==lc(fa[y])&&x==lc(y)||(y==rc(fa[y])&&x==rc(y)))rotate(y);
else rotate(x);
}
}
root=x;
}
void insert(int x,int v)
{
while(ch[x][k[x]<v])x=ch[x][k[x]<v];
ch[x][k[x]<v]=++ind;
fa[ind]=x;k[ind]=v;splay(ind);
}
inline int pre(int x)
{
int tmp=ch[x][];
while(ch[tmp][])tmp=ch[tmp][];
return k[tmp];
}
inline int suc(int x)
{
int tmp=ch[x][];
while(ch[tmp][])tmp=ch[tmp][];
return k[tmp];
}
int main()
{
int t;int n;
int ans=;
scanf("%d",&n);
if(scanf("%d",&t)==-)t=;
root=;k[root]=t;
ans=t;
insert(root,inf);insert(root,-inf);
for(int i=;i<=n;i++)
{
if(scanf("%d",&t)==-)t=;
insert(root,t);
int a=pre(root);int b=suc(root);
ans+=min(t-a,b-t);
}
printf("%d\n",ans);
return ;
}

bzoj 1588 splay模板题的更多相关文章

  1. bzoj 3224 splay模板题4

    再刷水题我就废了... #include<iostream> #include<cstdio> #include<algorithm> #include<cs ...

  2. bzoj 3223 splay模板题3

    水题...貌似理解splay怎么维护数列了... 每个点维护一个size,它的位置就是它的size,区间翻转的话可以打标记,find的时候push_down,交换左右子树. #include<i ...

  3. bzoj 1208 splay模板题2

    自己yy了找前驱和后继,学了学怎么删除...(反正就是练模板) #include<iostream> #include<cstdio> #include<cstring& ...

  4. BZOJ 1588 平衡树 模板题

    Treap: //By SiriusRen #include <cstdio> #include <algorithm> using namespace std; int si ...

  5. 【BZOJ 3196】二逼平衡树 线段树套splay 模板题

    我写的是线段树套splay,网上很多人写的都是套treap,然而本蒟蒻并不会treap 奉上sth神犇的模板: //bzoj3196 二逼平衡树,支持修改某个点的值,查询区间第k小值,查询区间某个值排 ...

  6. 【BZOJ 3188】【Coci 2011】Upit Splay模板题

    转啊转终于转出来了,然而我的模板跟陈竞潇学长的模板一模一样,还是太弱啊,第一次用指针. #include<cstdio> #include<cstring> #include& ...

  7. BZOJ 1208 &lbrack;HNOI2004&rsqb;宠物收养所 &vert; SPlay模板题

    题目: 洛谷也能评 题解: 记录一下当前树维护是宠物还是人,用Splay维护插入和删除. 对于任何一次询问操作都求一下value的前驱和后继(这里前驱和后继是可以和value相等的),比较哪个差值绝对 ...

  8. BZOJ 1588&colon; Treap 模板

    1588: [HNOI2002]营业额统计 Time Limit: 5 Sec  Memory Limit: 162 MBSubmit: 12171  Solved: 4352 Description ...

  9. BZOJ 3224 平衡树模板题

    Treap: //By SiriusRen #include <cstdio> #include <algorithm> using namespace std; int n, ...

随机推荐

  1. Linux上的SQL Server的起步

    我们知道,几个星期前,微软发布了在Linux上直接运行的SQL Server第一个公开CTP版本!因此,对我来说,是时候跨界在Linux上安装我的第一个SQL安装,这样的话,我就可以在Linux上折腾 ...

  2. SQL 行列转换简单示例

    SQLSERVER 2005 以后提供了新的方式进行行列转换,下面是一个实例供参考: if object_id('tb') is not null drop table tbTest go ),季度 ...

  3. ABAP&lowbar;常用函数整理&lowbar;傻X版

    输出前导0:CONVERSION_EXIT_ALPHA_INPUT 单位转换:CONVERSION_EXIT_CUNIT_INPUT 单位换算:UNIT_CONVERSION_SIMPLE 修改订单组 ...

  4. Android-关于android&colon;scrollbarStyle属性

    1. activity_maim.xml <LinearLayout xmlns:android="http://schemas.android.com/apk/res/android ...

  5. RTP&comma; RTCP&comma; RTSP 协议介绍

    流媒体是边下载边播放的方式, 是视频会议.IP电话等应用场合的技术基础.           为什么TCP/IP协议就不能满足多媒体通信的要求呢?因为TCP有以下4个特点:1.TCP重传机制2.TCP ...

  6. Maven deploy时报Fatal error compiling&colon; tools&period;jar not found错误的问题处理

    摘自:http://blog.csdn.net/achilles12345/article/details/19046061 在Eclipse环境下,使用Maven进行deploy时发现报了该错误:F ...

  7. &lbrack;转载&rsqb; Oracle在windows下面的自动备份以及删除今天的脚本&period;&period;

    @echo off echo ================================================ echo Windows环境下Oracle数据库的自动备份脚本 echo ...

  8. 快速开方法(c语言)译文

    人们最早就在Quake3源代码中发现了类似如下的C代码,它可以快速的求1/sqrt(x),在3D图形向量计算方面应用很广. float invSqrt(float x) { float xhalf = ...

  9. vue&period;js 开发环境配置

    1. node.js环境(npm包管理器) 下载: https://nodejs.org/en/download/current/ 下载解压版的方便 添加path环境后运行 npm包管理器,是集成在n ...

  10. Bootstrap导航栏实例讲解

    导航栏是一个很好的功能,是 Bootstrap 网站的一个突出特点.导航栏是响应式元组件就,作为应用程序或网站的导航标题.导航栏在移动设备的视图中是折叠的,随着可用视口宽度的增加,导航栏也会水平展开. ...