可持久化可以维护数据结构的历史版本。对于一个字典树,如果更改一个元素,暴力做法是复制一个树,让后在树上修改。其实,这样是有很多个一定一样的点是浪费的,真正被修改的是\(\log_2n\)个点,\(2\log_2n\)条边。优点:大大减低时间复杂度，还支持在线做。缺点:不能传懒

前言：题单在此：HL平衡树0701-题单-洛谷|计算机科学教育新生态(luogu.com.cn)平衡树什么是平衡树？首先我们需要知道二叉查找树的内容。二叉查找树（BST：BinarySearchTree)首先，他是一棵二叉树其次，他的左子树的权值<根节点的权值<右子树的权值最后，也是最重要的，他的中序遍历

权值线段树#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,

线段树是一种维护区间和等功能的数据结构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

题目传送门前置知识无旋treap解法与luoguP3391【模板】文艺平衡树不同的是本题翻转后需要放到整个序列的末尾。由于需要翻转后放到末尾，故无旋Treap在维护文艺平衡树的过程中合并时跳着合并即可。代码#include<bits/stdc++.h>usingnamespacestd;#definelllong

CF240F：https://www.luogu.com.cn/problem/CF240F题目大意：给定一个长为n的由a到z组成的字符串,有m次操作，每次操作将[l,r]的字符串进行重排，得到字典序最小的字符串，输出m次操作后的字符串。大致思路：1.首先我们要想区间内的字典序最小的回文串要怎么构造。回文串无非就两种类型：有一

点击查看代码#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(

线段树合并前置知识权值线段树，动态开点线段树简单说明一下，权值线段树就是以值域开的一棵线段树，而动态开点就是因为值域过大导致线段树开不下，于是开一棵残疾的线段树。线段树合并模板例：给定两个数列\(a,b\)，求\(\suma_i+b_i\)当然我只是为了引出模板。代码(\(x\)表

线段树常见操作build建树update更新query查询pushup向上回溯pushdown向下延迟更新(延迟标记)建线段树：//预编译命令，做符号代换#definelson(gjd<<1)#definerson(gjd<<1|1)//gjd表示当前结点，[l,r]表示区间范围voidbuild(intgjd,intl,intr){tree[gjd]

概述FHQTreap基于Treap发明的“无旋Treap”，代码短，易理解且速度快（在OI算是很优秀的算法了）。FHQTreap核心函数只有两个，分别是分裂和合并。字面意思，就是将某一棵二叉查找树按某种要求分裂成两个或将两个合并成一个。实现变量维护变量名功能root记录所维护

#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

#618.【JOISC2021】聚会2就是相当于选中的点在整棵树上的重心首先，当\(i\)为奇数时，答案为\(1\)当\(i\)为偶数时，可以将选中的点分为两个子树，分别记其根节点为\(x\)和\(y\)那么可以发现，所以合法的\(x\)和\(y\)构成一个连通块，那么当前答案就是连通块的直径，且随着\(i\)的增大，连通

在洛谷中查看前言将边权转化到点权的树剖，很好理解，但我就说说线段树部分。原本想做P1505[国家集训队]旅游的，但是发现它需要边权转化点权，所以先做了这题，于是代码里维护了\(minn\)、\(maxn\)、\(sum\)。包含内容：线段树部分怎么写、本题随机数据生成器线段树怎么写先试着

[HAOI2012]高速公路题解题目链接题目要求我们求期望，先考虑一下求期望的公式。根据期望的定义得：期望费用\(E_v=\dfrac{所有可能路线的总费用}{所有可能路线的数量}\).其中，所有可能路线的数量\(=C_{R-L+1}^2=(R-L+1)(R-L)\)，可以在常数时间内计算。（这里用大写的\(L\)，\(

[NOI2021]轻重边转化一下题意：每次给一条链染色，查一条链从\(x\)到\(y\)有几条边两端颜色相同。那这个随便树剖线段树就好了。也可以LCT，码量可能要小点。#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<vector>usingnamespace

题目链接: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

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5367官方题解：对于求“高山脉”长度，可以利用线段树。树节点中保存左高度连续长度，左高度连续区间的高度，左高度连续区间的状态（即是否高于第一个高度不同的山），右高度连续长度，右高度连续区间的高度，右高度连续区间的状态，每段区间内的“

enum{Maxn=1000005};structFHQTreap{intlson[Maxn],rson[Maxn],data[Maxn];intrnd[Maxn],sze[Maxn],root,tot,seed;FHQTreap(void){Ms(lson,0),Ms(rson,0),Ms(data,0);Ms(rnd,0),Ms(sze,0),root=tot=0,seed=1

AtCoderBeginnerContest223（D,E,F)D（拓扑排序）D大意就是有\(n\)个点，\(m\)个关系，其中关系是指\(u\)和\(v\),在排序里面使得\(u\)的位置再\(v\)的位置的前面要求找到一个排序满足上述条件的序列中字典序最小的那一个这个使用拓扑排序，并加上优先队列即可只要找到\(n\)个数，即为

structnode{intl,r,sum,lazy;node*lson,*rson;node(){l=r=sum=lazy=0;lson=rson

关于指针Splay目录关于指针Splay更好的阅读体验戳此进入写在前面操作核心节点UpdateGetDirRotateSplayInsertFindDeleteFindRankByValFindValByRankFindPreFindNxtCodeTOD

离线所有询问（按右端点排序），然后枚举右端点\(r\)。记\(X_l\)为\(a\)在区间\([l,r]\)中的最大值，\(Y_l\)为\(b\)在区间\([l,r]\)中的最大值。在枚举的过程中，对

继续搞点字符串。后缀平衡树。后缀平衡树，就是后缀数组上平衡树。它的中序遍历是后缀数组。但是它可以在线\(O(n\logn)\)构建，虽然码量大点。当然你可以先把后缀数组求

linkDescription定义\(a_{1,2,...,m}\)为好序列当且仅当\(\maxa_i+\mina_i>m\)，给出一个长度为\(n\)的序列，问最长好序列子段长度。有\(T\)次修改。\(n\le10^6,

好久没写博客了，主要是这玩意网上有点难搜到，就干脆糊了一个另外区间加操作的题见这个博客给定长为\(n\)的01序列，\(m\)个询问，第\(i\)次认为产生一个新版本\(i\)；要