用晚自习学了一下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模板题的更多相关文章
-
bzoj 3224 splay模板题4
再刷水题我就废了... #include<iostream> #include<cstdio> #include<algorithm> #include<cs ...
-
bzoj 3223 splay模板题3
水题...貌似理解splay怎么维护数列了... 每个点维护一个size,它的位置就是它的size,区间翻转的话可以打标记,find的时候push_down,交换左右子树. #include<i ...
-
bzoj 1208 splay模板题2
自己yy了找前驱和后继,学了学怎么删除...(反正就是练模板) #include<iostream> #include<cstdio> #include<cstring& ...
-
BZOJ 1588 平衡树 模板题
Treap: //By SiriusRen #include <cstdio> #include <algorithm> using namespace std; int si ...
-
【BZOJ 3196】二逼平衡树 线段树套splay 模板题
我写的是线段树套splay,网上很多人写的都是套treap,然而本蒟蒻并不会treap 奉上sth神犇的模板: //bzoj3196 二逼平衡树,支持修改某个点的值,查询区间第k小值,查询区间某个值排 ...
-
【BZOJ 3188】【Coci 2011】Upit Splay模板题
转啊转终于转出来了,然而我的模板跟陈竞潇学长的模板一模一样,还是太弱啊,第一次用指针. #include<cstdio> #include<cstring> #include& ...
-
BZOJ 1208 [HNOI2004]宠物收养所 | SPlay模板题
题目: 洛谷也能评 题解: 记录一下当前树维护是宠物还是人,用Splay维护插入和删除. 对于任何一次询问操作都求一下value的前驱和后继(这里前驱和后继是可以和value相等的),比较哪个差值绝对 ...
-
BZOJ 1588: Treap 模板
1588: [HNOI2002]营业额统计 Time Limit: 5 Sec Memory Limit: 162 MBSubmit: 12171 Solved: 4352 Description ...
-
BZOJ 3224 平衡树模板题
Treap: //By SiriusRen #include <cstdio> #include <algorithm> using namespace std; int n, ...
随机推荐
-
Linux上的SQL Server的起步
我们知道,几个星期前,微软发布了在Linux上直接运行的SQL Server第一个公开CTP版本!因此,对我来说,是时候跨界在Linux上安装我的第一个SQL安装,这样的话,我就可以在Linux上折腾 ...
-
SQL 行列转换简单示例
SQLSERVER 2005 以后提供了新的方式进行行列转换,下面是一个实例供参考: if object_id('tb') is not null drop table tbTest go ),季度 ...
-
ABAP_常用函数整理_傻X版
输出前导0:CONVERSION_EXIT_ALPHA_INPUT 单位转换:CONVERSION_EXIT_CUNIT_INPUT 单位换算:UNIT_CONVERSION_SIMPLE 修改订单组 ...
-
Android-关于android:scrollbarStyle属性
1. activity_maim.xml <LinearLayout xmlns:android="http://schemas.android.com/apk/res/android ...
-
RTP, RTCP, RTSP 协议介绍
流媒体是边下载边播放的方式, 是视频会议.IP电话等应用场合的技术基础. 为什么TCP/IP协议就不能满足多媒体通信的要求呢?因为TCP有以下4个特点:1.TCP重传机制2.TCP ...
-
Maven deploy时报Fatal error compiling: tools.jar not found错误的问题处理
摘自:http://blog.csdn.net/achilles12345/article/details/19046061 在Eclipse环境下,使用Maven进行deploy时发现报了该错误:F ...
-
[转载] Oracle在windows下面的自动备份以及删除今天的脚本..
@echo off echo ================================================ echo Windows环境下Oracle数据库的自动备份脚本 echo ...
-
快速开方法(c语言)译文
人们最早就在Quake3源代码中发现了类似如下的C代码,它可以快速的求1/sqrt(x),在3D图形向量计算方面应用很广. float invSqrt(float x) { float xhalf = ...
-
vue.js 开发环境配置
1. node.js环境(npm包管理器) 下载: https://nodejs.org/en/download/current/ 下载解压版的方便 添加path环境后运行 npm包管理器,是集成在n ...
-
Bootstrap导航栏实例讲解
导航栏是一个很好的功能,是 Bootstrap 网站的一个突出特点.导航栏是响应式元组件就,作为应用程序或网站的导航标题.导航栏在移动设备的视图中是折叠的,随着可用视口宽度的增加,导航栏也会水平展开. ...