BZOJ 1014: [JSOI2008]火星人prefix( splay + hash )
用splay维护序列, 二分+hash来判断LCQ..#include<bits/stdc++.h>using namespace std;typedef unsigned long long ull;const int maxn = 100009;const int P = 10001...
【BZOJ4864】神秘物质 [Splay]
神秘物质Time Limit: 10 Sec Memory Limit: 256 MBDescriptionInputOutputSample InputSample Output1215HINTMain idea每个点有一个权值，维护一个结构，支持合并相邻两点，删除单点，加入单点，查询区间子集极...
【BZOJ1500】[NOI2005]维修数列 Splay
【BZOJ1500】[NOI2005]维修数列DescriptionInput输入的第1 行包含两个数N 和M(M ≤20 000)，N 表示初始时数列中数的个数，M表示要进行的操作数目。第2行包含N个数字，描述初始时的数列。以下M行，每行一条命令，格式参见问题描述中的表格。任何时刻数列中最多含有5...
【splay】文艺平衡树 BZOJ 3223
Description您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1Input第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2……n-1,n) m表...
洛谷P4219 [BJOI2014]大融合（LCT，Splay）
LCT维护子树信息的思路总结与其它问题详见我的LCT总结思路分析动态连边，LCT题目跑不了了。然而这题又有点奇特的地方。我们分析一下，查询操作就是要让我们求出砍断这条边后，x和y各自子树大小的乘积。掌握了LCT如何维护虚子树信息和后，做法就很清晰了。split(x,y)后，输出x的虚子树和+1与y的...
splay最终模板
来自wjmzbmr的splay模板#include<cstdio>#include<iostream>#include<algorithm>using namespace std; + ;;struct Node { Node*ch[], *p; in...
【数据结构】平衡树splay和fhq—treap
1.BST二叉搜索树顾名思义，它是一棵二叉树。它满足一个性质：每一个节点的权值大于它的左儿子，小于它的右儿子。当然不只上面那两种树的结构。那么根据性质，可以得到该节点左子树里的所有值都比它小，右子树的都比它大。而平衡树都是基于BST的。为什么叫做平衡树？对于数的操作可能会破坏BST的性质，这时会进行...
【BZOJ3224】Tyvj 1728 普通平衡树 Splay
Description您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：1. 插入x数2. 删除x数(若有多个相同的数，因只删除一个)3. 查询x数的排名(若有多个相同的数，因输出最小的排名)4. 查询排名为x的数5. 求x的前驱(前驱定义为小于x，且最大的数)6. 求x的...
bzoj 1014 [JSOI2008]火星人prefix——splay+哈希
题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1014用splay维护字符串，每个点记录子树的哈希值，然后二分查询。二分不是把两个点的哈希值拿出来二分！因为取模了所以不能还原；因为splay维护了字符串，所以二分答案后把对应一段转出来看看哈希...
BZOJ1014: [JSOI2008]火星人prefix(splay 二分 hash)
题意题目链接Sol一眼splay + 二分hash，不过区间splay怎么写来着呀试着写了两个小时发现死活不对看了一下yyb的代码发现自己根本就不会splay。。。。// luogu-judger-enable-o2#include<bits/stdc++.h>#define ull u...
UOJ#55. 【WC2014】紫荆花之恋 点分树 替罪羊树 平衡树 splay Treap
原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ55.html题解做法还是挺容易想到的。但是写的话……首先这种题如果只要求一棵树中的满足条件的点数（不需要在加点的同时维护答案），那么显然可以点分治：假设当前点分中心为 x，设点 y 与 x 的距离为 d[y...
hiho #1329 : 平衡树·Splay
#1329 : 平衡树·Splay时间限制:10000ms单点时限:1000ms内存限制:256MB描述小Ho：小Hi，上一次你跟我讲了Treap，我也实现了。但是我遇到了一个关键的问题。小Hi：怎么了？小Ho：小Hi你也知道，我平时运气不太好。所以这也反映到了我写的Treap上。小Hi：你是说你随...
【NOI2004】郁闷的出纳员（splay）
题面DescriptionOIER公司是一家大型专业化软件公司，有着数以万计的员工。作为一名出纳员，我的任务之一便是统计每位员工的工资。这本来是一份不错的工 作，但是令人郁闷的是，我们的老板反复无常，经常调整员工的工资。如果他心情好，就可能把每位员工的工资加上一个相同的量。反之，如果心情不好，就可能...
bzoj 1588 splay模板题
用晚自习学了一下splay模板，没想象中那么难，主要是左旋和右旋可以简化到一个函数里边，减少代码长度。。。 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm>...
自我易错点总结： SPLAY 相关
自我易错点总结： SPLAY 相关 下传标记 不能只考虑当前层往子层传标记，有可能下传时同层不同时标记冲突，记得考虑。 递归改递推 形参与实参 改动时记得梳理变量顺序，不要生搬递推的式子。 先下传标记，后判断循环条件 自我易错点总结系列长(tuo)期(yan)更新...
【BZOJ 3196】二逼平衡树 线段树套splay 模板题
我写的是线段树套splay，网上很多人写的都是套treap，然而本蒟蒻并不会treap奉上sth神犇的模板：//bzoj3196 二逼平衡树，支持修改某个点的值，查询区间第k小值，查询区间某个值排名，查询区间某个值值前驱、后继。查询第k小值是log^3(n)的，其他都是log^2(n)的#inclu...
BZOJ3224/洛谷P3391 - 普通平衡树(Splay)
BZOJ链接 洛谷链接题意简述模板题啦~代码//普通平衡树(Splay)#include <cstdio>int const N=1e5+10;int rt,ndCnt;int ch[N][2],fa[N],val[N],siz[N],cnt[N];int wh(int p) {retu...
Hihocoder 1329 平衡树·Splay（平衡树）
Hihocoder 1329 平衡树·Splay（平衡树）Description小Ho：小Hi，上一次你跟我讲了Treap，我也实现了。但是我遇到了一个关键的问题。小Hi：怎么了？小Ho：小Hi你也知道，我平时运气不太好。所以这也反映到了我写的Treap上。小Hi：你是说你随机出来的权值不太好，从而...
【阶梯报告】洛谷P3391【模板】文艺平衡树 splay
【阶梯报告】洛谷P3391【模板】文艺平衡树 splay题目链接在这里[链接](https://www.luogu.org/problemnew/show/P3391)最近在学习splay，终于做对了这道模版题，虽然不是很难的样子。~~但是我一开始并不会做，而且看完题解之后还打错一直打不对，调试了很...
【转】 史上最详尽的平衡树(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...