【转】 史上最详尽的平衡树(splay)讲解与模板（非指针版spaly）
ORZ原创Clove学姐：变量声明：f[i]表示i的父结点，ch[i][0]表示i的左儿子，ch[i][1]表示i的右儿子，key[i]表示i的关键字（即结点i代表的那个数字），cnt[i]表示i结点的关键字出现的次数（相当于权值），size[i]表示包括i的这个子树的大小；sz为整棵树的大小，ro...
BZOJ1500: [NOI2005]维修数列[splay ***]
以前写过这道题了，但我把以前的内容删掉了，因为现在感觉没法看重写！题意：维护一个数列，支持插入一段数，删除一段数，修改一段数，翻转一段数，查询区间和，区间最大子序列splay序列操作裸题需要回收节点编号，所以用到$sz和nw()$，通常维护序列是不用sz的splay维护的是这个序列，不再存在平衡树左...
HDU1890 Robotic Sort[splay 序列]
Robotic SortTime Limit: 6000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3913 Accepted Submission(s): 17...
EZOJ 网同14(蛋蛋与北大信科-Splay的颜色分离,寻找结点所在子树)
蛋蛋与北大信科总时限10s内存限制256MB出题人lydrainbowcat提交情况1/25背景琰琰（孩纸们读作：蛋蛋）是妙峰书苑的一名萌萌哒教师，她的夫君（孩纸们称之为：北大信科）是北京大学信息科学技术学院的毕业生。无聊之余，蛋蛋与北大信科就成了孩纸们调侃的对象。描述宝哥和宝妹是孩纸们当中一对恩爱...
【bzoj1552/3506】[Cerc2007]robotic sort splay翻转，区间最值
【bzoj1552/3506】[Cerc2007]robotic sort Description Input 输入共两行，第一行为一个整数N，N表示物品的个数，1<=N<=100000。第二行为N个用空格隔开的正整数，表示N个物品最初排列的编号。 Outp...
bzoj 1552: [Cerc2007]robotic sort && bzoj 3506: [Cqoi2014]排序机械臂（splay区间翻转）
1552: [Cerc2007]robotic sort Time Limit: 5 Sec Memory Limit: 64 MB Submit: 1206 Solved: 460 [ Submit][ Status][ Discuss] Description ...
BZOJ 1552: [Cerc2007]robotic sort/3506: [Cqoi2014]排序机械臂 splay
1552: [Cerc2007]robotic sort Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 1273 Solved: 488 [Submit][Status][Discuss] Description Input ...
bzoj3506&1552 [Cerc2007][Cqoi2014]robotic sort 排序机械臂（splay）
bzoj3506&1552 [Cerc2007][Cqoi2014]robotic sort 排序机械臂 原题地址： http://www.lydsy.com/JudgeOnline/problem.php?id=3506 http://www.lydsy.com/JudgeOnlin...
洛谷 P3391 【模板】文艺平衡树（Splay）
题目背景这是一道经典的Splay模板题——文艺平衡树。题目描述您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1输入输出格式输入格式：第一行为n,m n表示初始序列有n...
bzoj1503[NOI2004]郁闷的出纳员——Splay
题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1503 好奇怪呀！为什么而TLE？ 各种修改终于卡时过了。可是大家比我快多了呀？难道是因为自己把相同节点弄成一个节点、记了一个cnt的缘故？ #include<iostream&...
BZOJ 2733: [HNOI2012]永无乡 [splay启发式合并]
2733: [HNOI2012]永无乡 题意：加边，询问一个连通块中k小值 终于写了一下splay启发式合并本题直接splay上一个节点对应图上一个点就可以了并查集维护连通性合并的时候，把size小的树的所有节点插入到size大的中，每个点最多插入log次，复杂度\(O(nlogn*insert\ ...
【BZOJ2733】永无乡[HNOI2012]（splay启发式合并or线段树合并）
题目大意：给你一些点，修改是在在两个点之间连一条无向边，查询时求某个点能走到的点中重要度第k大的点。题目中给定的是每个节点的排名，所以实际上是求第k小；题目求的是编号，不是重要度的排名。我一开始差点被这坑了。 网址：http://www.lydsy.com/JudgeOnline/problem.p...
[BZOJ]2733 [HNOI2012]永无乡(线段树合并/splay启发式合并)
//模拟赛里一道题要启发式合并，但我没想出来，我记得以前写过，结果发现原来是用线段树合并做的。。。 线段树合并： #include<cstdio>#include<cstring>#include<cstdlib>#include<cmath>...
[BZOJ1208] [HNOI2004] 宠物收养所 - splay
1208: [HNOI2004]宠物收养所 Time Limit: 10 Sec Memory Limit: 162 MB Submit: 6675 Solved: 2621 [ Submit][ Status][ Discuss] Description 最近，...
【BZOJ1208】[HNOI2004]宠物收养所 Splay
还是模板题，两颗splay，找点删即可。 1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #define inf 0x7fffffff 5 #define P ...
【Splay】 1208 [HNOI2004]宠物收养所
/************************************************************** Problem: 1208 User: 704035233 Language: C++ Result: Accepted Time:136 m...
[Scoi2014]方伯伯的OJ（动态开点splay）
开始没看数据范围差点以为是这题了：https://www.cnblogs.com/hfctf0210/p/10911340.html 然后看到n<=1e8，怎么这么大？ 所以这题需要用动态开点线段树或者动态开点splay，而我上面的那题写的树状数组，为了熟悉splay就用动态开点splay吧而...
splay详解（三）
前言上一节我们学习了splay所能解决的基本问题，这节我来讲一下splay怎么搞区间问题实现splay搞区间问题非常简单，比如我们要在区间$l,r$上搞事情，那么我们首先把$l$的前驱旋转到根节点再把$r$的后继旋转到根节点的右儿子那么此时根节点的右儿子的左儿子所代表的就是区间$l,r$这个应该比较...
Splay 的区间操作
学完Splay的查找作用，发现和普通的二叉查找树没什么区别，只是用了splay操作节省了时间开支。而Splay序列之王的称号可不是白给的。Splay真正强大的地方是他的区间操作。怎么实现呢？我们知道查找树的中序遍历是一个有序的序列。这个时候我们打破查找树左小右大的规则，而是把他的中序遍历作为我们的区...
3223. 文艺平衡树【平衡树-splay】
Description 您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1 Input 第一行为n,m n表示初始...