【BZOJ 3196】二逼平衡树 线段树套splay 模板题
我写的是线段树套splay，网上很多人写的都是套treap，然而本蒟蒻并不会treap奉上sth神犇的模板：//bzoj3196二逼平衡树，支持修改某个点的值，查询区间第k小值，查询区间某个值排名，查询区间某个值值前驱、后继。查询第k小值是log^3(n)的，其他都是log^2(n)的#includ...
HDU 1890 Robotic Sort（splay）
【题目链接】http://acm.hdu.edu.cn/showproblem.php?pid=1890【题意】给定一个序列，每次将i..P[i]反转，然后输出P[i]，P[i]定义为当前数字i的所在位置。相等的两个数排序后相对位置不变。【思路】由于相对位置不变，所以可以根据数值与位置重编号。依旧使...
Splay入门题目 [HNOI2002]营业额统计
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1588这道题貌似很多中做法，我先是用multiset交了一发，然后又写了一发splay。multiset做法，这个其实就是二分了，只是用set来保持加入一个元素时保持有序#include<...
Splay入门解析【保证让你看不懂（滑稽）】
来自两年后的提示本篇文章只是娱乐向的介绍性文章，可以进行初步理解。\(\text{Splay}\)如果需要严格的证明均摊复杂度参考势能分析。另外\(\text{Splay}\)依靠\(rotate\)来维护\(size\)等节点维护的值。如果代码中没有体现请不要忘记上面这句话。另外本文中很多内容经不...
splay入门教程
笔者一个数据结构的蒟蒻还是奇迹般的搞明白了splay的基本原理以及实现方法，所以写下这篇随笔希望能帮到像我当初一脸懵逼的人。我们从二叉查找树开始说起：二叉查找树是一棵二叉树，它满足这样一个性质：所有小于当前节点的点都在该节点的左子树上，所有大于当前节点的点都在该节点的右子树上。对于和当前节点一样大的...
【学习笔记】splay入门（更新中）
声明：本博客所有随笔都参照了网络资料或其他博客，仅为博主想加深理解而写，如有疑问欢迎与博主讨论✧｡٩(ˊᗜˋ)و✧*｡前言终于学习了spaly\(splay\)！听说了很久，因为dalao总是那这个开玩笑所以对它有深深的恐惧...但是学起来没有那么难啦，可能是因为提前学了替罪羊树？（学替罪羊树真的是...
bzoj 1588: [HNOI2002]营业额统计（splay入门）
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1588题解：这题如果用普通的bst的话是可以过时间差不多4s左右如果用splay的话是140ms。由于splay可以有序的插入，各种操作都不会改变中序遍历的结果，而且splay每次可以将插入的...
绝对是全网最好的Splay 入门详解——洛谷P3369&BZOJ3224: Tyvj 1728 普通平衡树 包教包会
平衡树是什么东西想必我就不用说太多了吧。百度百科：一个月之前的某天晚上，yuli巨佬为我们初步讲解了Splay，当时接触到了平衡树里的旋转等各种骚操作，感觉非常厉害。而第二天我调Splay的模板竟然就搞了一天，最后还是失败告终，只能CV了事，而Splay也成了我心中的一个心结，一直没法解决。在西安集...
【BZOJ3224】普通平衡树（splay）
题意：您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：1.插入x数2.删除x数(若有多个相同的数，因只删除一个)3.查询x数的排名(若有多个相同的数，因输出最小的排名)4.查询排名为x的数5.求x的前驱(前驱定义为小于x，且最大的数)6.求x的后继(后继定义为大于x，且最...
BZOJ4864 BeiJing 2017 Wc神秘物质（splay）
splay维护区间最大值、最小值、相邻两数差的绝对值的最小值即可。#include<iostream>#include<cstdio>#include<cmath>#include<cstdlib>#include<cstring>#inc...
【CF809D】Hitchhiking in the Baltic States（Splay，动态规划）
【CF809D】HitchhikingintheBalticStates（Splay，动态规划）题面CF洛谷题解朴素\(dp\)：设\(f[i][j]\)表示当前考虑到第\(i\)个元素，结尾位置是\(j\)的最大选择数。然而这样就很呆。换个状态：设\(f[i][j]\)表示当前考虑到第\(i\)个...
【CF809D】Hitchhiking in the Baltic States Splay
【CF809D】HitchhikingintheBalticStates题意：给你n个区间[li,ri]，让你选出从中一个子序列，然后在子序列的每个区间里都选择一个tj，满足$t_1<t_2<...<t_{len}$。最大化这个子序列的长度。$1\len\le3\cdot10^5,...
CF 809D Hitchhiking in the Baltic States——splay+dp
题目：http://codeforces.com/contest/809/problem/D如果值是固定的，新加入一个值，可以让第一个值大于它的那个长度的值等于它。如今值是一段区间，就对区间内的dp值都有影响；中间的那些的值变成了上一个的值+1，左边l处多了一个点，右边第一个大于等于r的点被删掉。用...
[P3369]普通平衡树(Splay版)
模板，不解释#include<bits/stdc++.h>usingnamespacestd;constintmxn=1e5+5;intfa[mxn],ch[mxn][2],sz[mxn],cnt[mxn],val[mxn],rt,tot;namespaceSplay{voidpush_...
Bzoj 1208: [HNOI2004]宠物收养所(splay)
1208:[HNOI2004]宠物收养所TimeLimit:10SecMemoryLimit:162MBDescription最近，阿Q开了一间宠物收养所。收养所提供两种服务：收养被主人遗弃的宠物和让新的主人领养这些宠物。每个领养者都希望领养到自己满意的宠物，阿Q根据领养者的要求通过他自己发明的一个...
BZOJ 1208 [HNOI2004]宠物收养所 | SPlay模板题
题目:洛谷也能评题解:记录一下当前树维护是宠物还是人,用Splay维护插入和删除.对于任何一次询问操作都求一下value的前驱和后继(这里前驱和后继是可以和value相等的),比较哪个差值绝对值小就好啦#include<cstdio>#include<algorithm>#i...
BZOJ 1208 [HNOI2004]宠物收养所：Splay（伸展树）
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1208题意：有一个宠物收养所，在接下来一段时间内会陆续有一些宠物进到店里，或是一些人来领养宠物。宠物和人的总数量为n。t=0代表宠物，t=1代表人。宠物和人分别有一个特点值a和b。有两种情况：...
bzoj3224 splay板子
开始学习新知识：splay——tree是个板子题，学习splay可以看博客https://blog.csdn.net/Clove_unique/article/details/50630280#include<iostream>#include<cstring>#includ...
BZOJ[NOI2004]郁闷的出纳员 | Splay板子题
题目:洛谷也能评测....还有我wa了10多次的记录233题解:不要想得太复杂,搞一个全局变量记录一下工资的改变量Delta,这样可以等询问的时候就输出val+Delta,然后插入的时候插入x-Delta不要想会不会有员工工资一样,直接插入就好,这样省不少代码量.对于降工资操作,插入一个min-De...
BZOJ 3224 Tyvj 1728 普通平衡树 | Splay 板子+SPlay详细讲解
下面给出Splay的实现方法(复杂度证明什么的知道是nlogn就可以啦)首先对于一颗可爱的二叉查找树,是不能保证最坏nlogn的复杂度(可以想象把一个升序序列插入)(二叉查找树保证左子树元素大小都小于根元素大小,根元素大小都小于右子树元素大小,且子树都是二叉查找树)所以我们需要一些非常巧妙的旋转操作...