POJ 3667 splay区间盘整运动
HotelTime Limit: 3000MS Memory Limit: 65536KTotal Submissions: 12446 Accepted: 5363DescriptionThe cows are journeying north to Thunder Bay in Canada t...
POJ 3481 splay模板
最后撸一发splay。之前用treap撸的，现在splay也找到感觉了，果然不同凡响，两者之间差别与精妙之处各有其精髓！真心赞一个！POJ平衡树的题目还是比较少，只能挑之前做过的捏一捏。但是收获很多，这一天做的题都是有一定普遍性的。#include <cstdio>#include &l...
平衡树简单教程及模板（splay, 替罪羊树, 非旋treap）
原文链接https://www.cnblogs.com/zhouzhendong/p/Balanced-Binary-Tree.html注意是简单教程，不是入门教程。splay1. 旋转：假设点 y 原是点 x 的 father，旋转操作可以在不改变中序遍历的基础上，将 y 变成 x 的儿子。例如：...
splay模板
点操作：splay树可以一个一个的插入结点，这样的splay树是有序树，结点权值大于左儿子小于右儿子这样就是点操作区间操作：还有就是可以自己建树，这样的splay树就不是按权值的有序树，它不满足结点权值大于左儿子小于右儿子，，但是它也是有顺序的，无论怎么伸展，把它的结点中序遍历结果就是原来的数组顺序...
bzoj 1014 splay维护hash值
被后缀三人组虐了一下午，写道水题愉悦身心。题很裸，求lcq时二分下答案就行了，写的不优美会被卡时。（写题时精神恍惚,不知不觉写了快两百行。。。竟然调都没调就A了。。。我还是继续看后缀自动机吧。。。） #include<iostream> #include<cstdio> #i...
【BZOJ-3196】二逼平衡树 线段树 + Splay （线段树套平衡树）
3196: Tyvj 1730 二逼平衡树Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 2271 Solved: 935[Submit][Status][Discuss]Description您需要写一种数据结构（可参考题目标题），来维护一个有序数...
BZOJ.1492.[NOI2007]货币兑换(DP 斜率优化 CDQ分治/Splay)
BZOJ洛谷如果某天能够赚钱，那么一定会在这天把手上的金券全卖掉。同样如果某天要买，一定会把所有钱花光。那么令\(f_i\)表示到第\(i\)天所拥有的最多钱数（此时手上没有任何金券），可以选择什么都不干，\(f_i=f_{i-1}\)；也可以从之前的某一天\(j\)花\(f_j\)的钱买金券，在第...
NOI2005维修数列 splay
好题，错了不知道多少遍。这题其他几个操作都是比较经典的，多了一个最大子序列的。这时候对于当前的区间，最大子序列，可能使左区间的最值，可能是右区间的最值，也可能是整个区间的。所以维护lx[],rx[],mx[]。lx[rt] = max(lx[l],sum[l]+key[rt]+max(0,lx[r]...
BZOJ_4516_[Sdoi2016]生成魔咒_后缀数组+ST表+splay
BZOJ_4516_[Sdoi2016]生成魔咒_后缀数组+ST表+splayDescription魔咒串由许多魔咒字符组成，魔咒字符可以用数字表示。例如可以将魔咒字符 1、2 拼凑起来形成一个魔咒串 [1,2]。一个魔咒串 S 的非空字串被称为魔咒串 S 的生成魔咒。例如 S=[1,2,1] 时，...
bzoj 1503郁闷的出纳员(splay)
1503: [NOI2004]郁闷的出纳员Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 11759 Solved: 4163[Submit][Status][Discuss]DescriptionOIER公司是一家大型专业化软件公司，有着数以万计的员工...
[知识点]平衡树之Splay
// 此博文为迁移而来，写于2015年7月18日，不代表本人现在的观点与看法。原始地址：http://blog.sina.com.cn/s/blog_6022c4720102w6rg.html1、前言 这玩意儿真的搞了我好久，当然前一阵子一直都没有去管它，最近直接参照了YML（@YMDr...
K：伸展树(splay tree)
伸展树（Splay Tree），也叫分裂树，是一种二叉排序树，它能在O(lgN)内完成插入、查找和删除操作。在伸展树上的一般操作都基于伸展操作：假设想要对一个二叉查找树执行一系列的查找操作，为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法， 在每...
BZOJ_1895_Pku3580 supermemo_Splay
BZOJ_1895_Pku3580 supermemo_SplayDescription给出一个初始序列fA1;A2;:::Ang，要求你编写程序支持如下操作： 1. ADDxyD：给子序列fAx:::Ayg的每个元素都加上D。例如对f1,2, 3,4,5g执行"ADD 241" 会得到f1,3,4...
HDU 3487 Play with Chain | Splay
Play with ChainTime Limit: 6000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) 【Problem Description】YaoYao is fond of playing his ...
【填坑】bzoj3224 splay裸题
人生第一道splay不出所料是一道裸题，一道水题，一道2k代码都不到的题 #include <cstdio> int root,N=,n,p,q; int fa[],c[][],size[],sp[]; void rot(int x) { int y=fa[x],k=(c[y][...
【BZOJ】1058: [ZJOI2007]报表统计（splay+set）
http://www.lydsy.com/JudgeOnline/problem.php?id=1058当复习一下splay。。。。做法很简单。。。。。观察得知每一次插入一个点只需要维护前后的绝对值观察得知min_sort_gap直接二分已经排好序的数组找到前驱后继更新即可（这里是个贪心，显然成立）...
BZOJ 3091: 城市旅行 [LCT splay 期望]
3091: 城市旅行Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 1454 Solved: 483[Submit][Status][Discuss]DescriptionInputOutputSample Input4 51 3 2 51 21 3...
在平衡树的海洋中畅游（三）——Splay
Preface由于我怕学习了Splay之后不直接写blog第二天就忘了，所以强行加了一波优先级。论谁是天下最秀平衡树，我Splay第一个不服。维护平衡只靠旋转。一言不合转死你由于平衡树我也介绍了两种Treap&&Scapegoat Tree，所以一些互通的东西也不讲了。这次的亮点主要...
BZOJ4864 BeiJing 2017 Wc神秘物质（splay）
splay维护区间最大值、最小值、相邻两数差的绝对值的最小值即可。#include<iostream>#include<cstdio>#include<cmath>#include<cstdlib>#include<cstring>#inc...
BZOJ_4864_[BeiJing 2017 Wc]神秘物质_Splay
BZOJ4864_[BeiJing 2017 Wc]神秘物质_SplayDescription21ZZ 年，冬。小诚退休以后， 不知为何重新燃起了对物理学的兴趣。 他从研究所借了些实验仪器，整天研究各种微观粒子。这一天， 小诚刚从研究所得到了一块奇异的陨石样本， 便迫不及待地开始观测。 在精密仪器的...