- 2024-12-24[学习笔记] splay
前置:二叉查找树在二叉查找树上做许多操作都十分方便。然而递归树的层数意味着时间复杂度为树高级别。当树是链状时,时间复杂度会退化。各类平衡树的存在大都为了使二叉查找树“平衡”,即高度不会超过\(\logn\)(\(n\)为树的结点个数)。如此以来,在二叉查找树上的操作就有了时间复杂
- 2024-11-27笔记:FHQ Treap 之三分裂
小知识点,但是好像没什么人写,所以写一篇。在NOIP之前积攒一点rp。需要的知识平衡树(FHQTreap)前言一般在写FHQTreap的时候,都是按照某个值或排名\(k\),将Treap分成小于等于和大于\(k\)的两棵树,我们将其称为二分裂。那么,所谓三分裂,就是将Treap按照小于、等于、大于
- 2024-11-26线段树
基本知识定义上线段树就是一种可以维护区间信息的数据结构,在原数列的基础上多加了一些点,一层一层往上合并的过程。特殊的就是打lazytag方式和其他的一些线段树处理方式。多种标记的时候需要分析优先级,比如加法和乘法的优先级。典型线段树区间加法乘法:考虑分配律,乘
- 2024-07-282024/07/28 每日一题
LeetCode699掉落的方块方法1:暴力classSolution:deffallingSquares(self,positions:List[List[int]])->List[int]:n=len(positions);ans=[0]*n#记录每个方块落下后的高度fori,(left0,widen0)inenumerate(positions):
- 2024-07-17小球掉落(C++)
#include<bits/stdc++.h>usingnamespacestd;structnode{ intid; booldata; intfather; intlson,rson;};nodetree[6000000];intd,i;intmain(){ cin>>d>>i; tree[1].father=0; tree[1].lson=2; tree[1].rson=3; tree[1].data=false;
- 2024-07-13[ZJOI2006] 三色二叉树 题解
[ZJOI2006]三色二叉树题解link趣题。首先我们把题目分成两部分:建树和dp求解。建树:观察发现,字符串中的第\(i\)个字符就代表图中的第\(i\)个节点。如果\(S_i=0\),直接跳过;如果\(S_i=1\),那么\(i+1\)是\(i\)唯一的子节点,在两点之间连边,然后继续递归建树即可。
- 2024-07-02可持久化 0/1 Trie
可持久化可以维护数据结构的历史版本。对于一个字典树,如果更改一个元素,暴力做法是复制一个树,让后在树上修改。其实,这样是有很多个一定一样的点是浪费的,真正被修改的是\(\log_2n\)个点,\(2\log_2n\)条边。优点:大大减低时间复杂度,还支持在线做。缺点:不能传懒
- 2024-07-02平衡樹專題Treap
前言:题单在此:HL平衡树0701-题单-洛谷|计算机科学教育新生态(luogu.com.cn)平衡树什么是平衡树?首先我们需要知道二叉查找树的内容。二叉查找树(BST:BinarySearchTree)首先,他是一棵二叉树其次,他的左子树的权值<根节点的权值<右子树的权值最后,也是最重要的,他的中序遍历
- 2024-06-01聊聊 普通平衡树 的 几种做法
权值线段树#include<bits/stdc++.h>usingnamespacestd;constintMAXN=5e5+10;intn,m,a[MAXN],x,y,op;//Segmenttree#definel(x)tree[x].ls#definer(x)tree[x].rs#definesum(x)tree[x].sumintSegmentsum;structSegmentTree{ intl,r,len,ls,rs,sum,
- 2024-05-26线段树结构体模板
线段树是一种维护区间和等功能的数据结构structSegTree{ structnode{ intl,r,sum,len,laz; }tree[N<<2]; inlinevoidpushdown(intu){ intlson=u<<1,rson=lson|1; tree[lson].laz+=tree[u].laz; tree[rson].laz+=tree[u].laz; tree[lson].sum+=tree[lson].len
- 2024-05-26UVA11922 Permutation Transformer 题解
题目传送门前置知识无旋treap解法与luoguP3391【模板】文艺平衡树不同的是本题翻转后需要放到整个序列的末尾。由于需要翻转后放到末尾,故无旋Treap在维护文艺平衡树的过程中合并时跳着合并即可。代码#include<bits/stdc++.h>usingnamespacestd;#definelllong
- 2024-05-25线段树维护区间字符的两道例题(CF240F CF558E)
CF240F:https://www.luogu.com.cn/problem/CF240F题目大意:给定一个长为n的由a到z组成的字符串,有m次操作,每次操作将[l,r]的字符串进行重排,得到字典序最小的字符串,输出m次操作后的字符串。大致思路:1.首先我们要想区间内的字典序最小的回文串要怎么构造。回文串无非就两种类型:有一
- 2024-05-08线~段~树
点击查看代码#include<bits/stdc++.h>#definelsonid<<1#definersonid<<1|1usingnamespacestd;constintN=1e6+12000;structnode{ intl,r,num; intma,mi;}tr[N<<2];inta[N];intn,m;stringstr;intans=0;intfrom,to;voidbuild(
- 2024-05-01数据结构--线段树合并
线段树合并前置知识权值线段树,动态开点线段树简单说明一下,权值线段树就是以值域开的一棵线段树,而动态开点就是因为值域过大导致线段树开不下,于是开一棵残疾的线段树。线段树合并模板例:给定两个数列\(a,b\),求\(\suma_i+b_i\)当然我只是为了引出模板。代码(\(x\)表
- 2024-02-20线段树—模板
线段树常见操作build建树update更新query查询pushup向上回溯pushdown向下延迟更新(延迟标记)建线段树://预编译命令,做符号代换#definelson(gjd<<1)#definerson(gjd<<1|1)//gjd表示当前结点,[l,r]表示区间范围voidbuild(intgjd,intl,intr){tree[gjd]
- 2023-10-23Treap
概述FHQTreap基于Treap发明的“无旋Treap”,代码短,易理解且速度快(在OI算是很优秀的算法了)。FHQTreap核心函数只有两个,分别是分裂和合并。字面意思,就是将某一棵二叉查找树按某种要求分裂成两个或将两个合并成一个。实现变量维护变量名功能root记录所维护
- 2023-10-19进行一个脑洞治疗仪的保存
#include<iostream>#include<fstream>#include<algorithm>//#defineintlonglongusingnamespacestd;structnode_t{ intl,r; intlval,rval,val; intsum,tag;#definel(x)tr[x].l#definer(x)tr[x].r#definelval(x)tr[x].lval#de
- 2023-10-10[UOJ618]【JOISC2021】聚会 2
#618.【JOISC2021】聚会2就是相当于选中的点在整棵树上的重心首先,当\(i\)为奇数时,答案为\(1\)当\(i\)为偶数时,可以将选中的点分为两个子树,分别记其根节点为\(x\)和\(y\)那么可以发现,所以合法的\(x\)和\(y\)构成一个连通块,那么当前答案就是连通块的直径,且随着\(i\)的增大,连通
- 2023-09-17Luogu-P4315 月下“毛景树”
在洛谷中查看前言将边权转化到点权的树剖,很好理解,但我就说说线段树部分。原本想做P1505[国家集训队]旅游的,但是发现它需要边权转化点权,所以先做了这题,于是代码里维护了\(minn\)、\(maxn\)、\(sum\)。包含内容:线段树部分怎么写、本题随机数据生成器线段树怎么写先试着
- 2023-08-28[HAOI2012] 高速公路 题解
[HAOI2012]高速公路题解题目链接题目要求我们求期望,先考虑一下求期望的公式。根据期望的定义得:期望费用\(E_v=\dfrac{所有可能路线的总费用}{所有可能路线的数量}\).其中,所有可能路线的数量\(=C_{R-L+1}^2=(R-L+1)(R-L)\),可以在常数时间内计算。(这里用大写的\(L\),\(
- 2023-07-13NOI2021 题解
[NOI2021]轻重边转化一下题意:每次给一条链染色,查一条链从\(x\)到\(y\)有几条边两端颜色相同。那这个随便树剖线段树就好了。也可以LCT,码量可能要小点。#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<vector>usingnamespace
- 2023-05-31牛客想开了大赛2 题解
题目链接:https://ac.nowcoder.com/acm/contest/907#question A.【六】平面公式:(n*n+n)/2+1,n为直线数目B.【一】n的约数枚举质因子和每个质因子的个数,显然个数肯定从多到少。#include<bits/stdc++.h>typedeflonglongll;usingnamespacestd;constintmx=1e4+10;in
- 2023-05-29hdu 5367(线段树+区间合并)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5367官方题解:对于求“高山脉”长度,可以利用线段树。树节点中保存左高度连续长度,左高度连续区间的高度,左高度连续区间的状态(即是否高于第一个高度不同的山),右高度连续长度,右高度连续区间的高度,右高度连续区间的状态,每段区间内的“