wjyppm's Blog

点分治 点分治，又称淀粉质，淀粉脂。是用来解决树上路径问题。 1.例题引入 P3806 点分治板子 给定一棵有 n 个点的树，询问树上距离为 k 的点对是否存在。 就是求无根树中长度为k的路径数目 暴力做法：考虑枚举每个点，每一次都统计距离路径。时间复杂度O(n2)O(n^2)O(n2) 我们假设一个点为根节点rtrtrt，把它先转化为有根树 考虑对每个路径进行统计，路径统计可以分为2类路径，一个路径是过当前点rtrtrt，一个路径是不过当前点rtrtrt。 这样分类是显然正确的，而且对于不经过ttt的路径，它们一定在ttt的某个子节点所构成的子树中。 对于前者，设dis[u]dis[u]dis[u]表示从节点uuu到根节点rtrtrt的路径长度，则uuu到vvv的路径长度就是dis[u]+dis[v]dis[u]+dis[v]dis[u]+dis[v] 对于后者，我们可以考虑重新统计子树，找到子树的根，让后再子树求第一类路径。 就是分治的思想，点分治途径中每一层所有递归都对点仅处理一次，即时间复杂度O(T×N)O(T\times N)O(T×N) ，TTT即子树大小。 ...

0.前情提要 在学长的课上听到了颜色段覆盖问题，顺手讲了个ODT，当时的我以为就是一个可爱的数据结构，但是学下来发现确实很可爱(｡・ω・｡) CF896C——ODT的起源 你需要知道——STL的set怎么用（cppreference） 对就这些。 1.什么是珂朵莉树 珂朵莉树，又称ODT（老司机树），是一种利用set的暴力数据结构，用于解决区间问题的数据结构。 2.珂朵莉树可以解决什么问题 区间推平问题出现的时候我们就可以用珂朵莉树了。她高效的基础是当数据随机生成的时候，复杂度是正确的（见下文），但是若没说，你就要开赌，这个很容易被构造数据卡掉。 3.珂朵莉树的构造 借用一下大佬的图 对于珂朵莉树的节点，我们维护的是一个数值相同的区间，如上图。我们考虑维护一个三元组(l,r,val)(l,r,val)(l,r,val)，其中l和r是数值相同区间的左右端点，val就是这个区间对应的数值，那么每个相同数列的区间就可以浓缩为一个节点，如下图 当然在维护区间的时候我们要满足区间左端点和右端点都样单调递增，这里只需要比较左端点就可以了。 代码如下 当然对于CF896C我们...

吉司机线段树 0.吉司机的前言 1.介绍 吉司机线段树主要用于2件事，一个是区间最值修改，一个是区间历史最值维护。 2.区间最值 给定一个长度为n的数列A，接着有m次操作 区间[l,r]中所有数变为min(Ai,x)min(A_i,x)min(Ai​,x) 询问区间[l,r]和 使用O(nlog⁡n)数据结构O(n\log n)数据结构O(nlogn)数据结构 用线段树解题一般我们使用lazytag来实现高效的时间复杂度。但是本题怎么设计？如果用一个tag处理区间最值，另一个处理区间和，但是这个和修改区间最值没有任何直接关系，不能这么简单处理。 吉司机线段树将这一类区间最值进行了通用转化方法，时间复杂度达到了O(nlog⁡n)O(n\log n)O(nlogn)。首先维护如下标记 区间最大值mx 区间最大值出现次数mxcnt 区间次大值se 区间和sum 考虑区间最值修改操作，即用min(Ai,x)min(A_i,x)min(Ai​,x)替换区间[L,R][L,R][L,R]的每个节点aia_iai​，首先找到对应区间，让后暴力搜索，我们搜到某个节点时，会...

****# 0.前言 前缀最大值就是指从序列开头到某个位置，所有元素的最大值喵~ ——Deepseek 即如下 max⁡j=1iaj\max\limits_{j=1}^i a_j j=1maxi​aj​ 比如序列 [3,1,4,1,5][3, 1, 4, 1, 5][3,1,4,1,5]，它的前缀最大值序列就是 [3,3,4,4,5][3, 3, 4, 4, 5][3,3,4,4,5]。 1.正文 看如下题 P4198 小A在平面上(0,0)点的位置，第i栋楼房可以用一条连接(i,0)和(i,Hi)的线段表示，其中Hi为第i栋楼房的高度。如果这栋楼房上任何一个高度大于0的点与(0,0)的连线没有与之前的线段相交，那么这栋楼房就被认为是可见的。 施工队的建造总共进行了M天。初始时，所有楼房都还没有开始建造，它们的高度均为0。在第i天，建筑队将会将横坐标为Xi的房屋的高度变为Yi(高度可以比原来大—修建，也可以比原来小—拆除，甚至可以保持不变—建筑队这天什么事也没做)。请你帮小A数数每天在建筑队完工之后，他能看到多少栋楼房？ 我们把样例画出来，左图任何情况下都只为1，...

0.前言 这里没有负边权，SPFA请右转最短路。 本文章基于路径规划之 A* 算法的精致动图以及算法竞赛等数据以及个人鄙见，望大佬提出建议qwq。 1. 前人的铺垫 1.1.Dijkstra算法 这不是图论的最短路吗？ 其实这个算法就是用来寻找图形中节点之间的最短路径 考虑这样一种场景，在一些情况下，图形中相邻节点之间的移动代价并不相等。例如，游戏中的一幅图，既有平地也有山脉，那么游戏中的角色在平地和山脉中移动的速度通常是不相等的。 在Dijkstra算法中，需要计算每一个节点距离起点的总移动代价。同时，还需要一个优先队列结构。对于所有待遍历的节点，放入优先队列中会按照代价进行排序。 在算法运行的过程中，每次都从优先队列中选出代价最小的作为下一个遍历的节点。直到到达终点为止。 下图中绿色部分代表有额外点权（默认大于1）： 当图形为网格图且点权均为1时，降为BFS 这里贴一个Dijkstra算法的单源最短路模板： 12345678910111213141516171819202122232425262728struct node{ int pos,dis...

这里是块状数组 1.引入 分块是一种思想，把一个整体划分为若干个等长的小块，对整块整体处理，打标记。零散块暴力处理。可以做到均摊O(n)O(\sqrt{n})O(n​)的询问时间复杂度，总时间复杂度O(nn)O(n\sqrt{n})O(nn​)的一个优雅的暴力思想 我们将一个长度为nnn的数组分成lenlenlen个块，那么每个块的长度就是nlen\frac{n}{len}lenn​，一般来说这个lenlenlen取n\sqrt{n}n​,是需要自己用基本不等式去算出来的，但是一般比赛中手算一下理论复杂度，只要块长n\sqrt{n}n​能过就行。 为啥非要取n\sqrt{n}n​？因为nn=n\frac{n}{\sqrt{n}}=\sqrt{n}n​n​=n​,显然用基本不等式可以证明 以下是对1~16进行分块，分块实质上就是3层树，第二层就是块，每个块的子树共有n\sqrt{n}n​个孩子节点。只不过，块状数组最顶层的信息不用维护。 我们对于一次区间操作，可能有如下的可能 我们所操作的区间左右端点刚好在一个块里，这时候我们就可以暴力操作。但是我们要注意如果所修改的信息对...

0.引入的引入 数位是指把一个数字按照个、十、百、千等等一位一位地拆开，关注它每一位上的数字。如果拆的是十进制数，那么每一位数字都是 0~9，其他进制可类比十进制。 而数位DP，就是解决在区间[L,R][L,R][L,R]这个范围内，求满足某种约束的数字的数量或总和或乘积或平方这一类问题。 两种写法，一种是记忆化搜索，一种是迭代写法。这里是记忆化搜索，优点是好写好维护。 1.由例题引入数位DP 数位DP有一个通用的技巧，就是利用前缀和的思想，先求出[1,R][1,R][1,R]区间的满足约束的数字答案，再处理[1,L−1][1,L-1][1,L−1]的满足约束的数字答案，这样Ans[R]−Ans[L−1]Ans[R]-Ans[L-1]Ans[R]−Ans[L−1]所求得的区间就是[L,R][L,R][L,R]区间的答案。 所以我们要求解的内容就变为了求[0/1,x][0/1,x][0/1,x]这一区间满足限定的答案，其实0/1表示可以区间取0或1作为开始 在代码中表现为 a[1...len]a[1...len]a[1...len]表示将数分解成R进制（一般为10进制或者2进...

1.概念 四边形不等式是对一个二元函数定义：w(l,r)w(l,r)w(l,r)。这里的w(l,r)w(l,r)w(l,r)可以看作价值，权值或着价格都可以。 对于任意a≤b≤c≤da\le b\le c\le da≤b≤c≤d ，若都有w(a,d)+w(b,c)≥w(a,c)+w(b,d)w(a,d)+w(b,c)\ge w(a,c)+w(b,d)w(a,d)+w(b,c)≥w(a,c)+w(b,d)，我们就称w(l,r)w(l,r)w(l,r)满足四边形不等式，可以简单记为：”交叉小于包含“。 同时有结论，对于a≤ba\le ba≤b，有w(a,b−1)+w(a+1,b)≤w(a,b)+w(a+1,b−1)w(a,b-1)+w(a+1,b)\le w(a,b)+w(a+1,b-1)w(a,b−1)+w(a+1,b)≤w(a,b)+w(a+1,b−1)。 结论：若两个函数之间满足四边形不等式，那么和也满足四边形不等式。 话说为啥叫四边形不等式： AD+BC≥AC+BDAD+BC\ge AC+BDAD+BC≥AC+BD，这个显然在初中是学过的。 反四边形不等式： 就是符号调换...

0.前言 本文章例题出自于蓝书，优化方案来自许多博客（但我忘了呜呜呜） 1.单调队列概念与怎么优化 单调队列，我们先来看他是用来干什么的。 单调队列主要用于维护两端指针单调不减的区间最值。 ——oiwiki 对于一般的特殊DP方程，我们可以进行优化。 他优化的是下面的一类DP方程，其中： 得到的方程：f[i]=min⁡L(i)≤j≤R(i)(f[j]+a[i]+b[j])\text{得到的方程：} f[i]=\min\limits_{L(i)\le j \le R(i)}{(f[j]+a[i]+b[j])} 得到的方程：f[i]=L(i)≤j≤R(i)min​(f[j]+a[i]+b[j]) 因为i是外层循环定值，变形为：f[i]=min⁡L(i)≤j≤R(i)(f[j]+b[j])+a[i]\text{因为i是外层循环定值，变形为：} f[i]=\min\limits_{L(i)\le j \le R(i)}(f[j]+b[j])+a[i] 因为i是外层循环定值，变形为：f[i]=L(i)≤j≤R(i)min​(f[j]+b[j])+a[i] 其中min可以替换为...

1.前言 本文章图较多！ 动态规划在转移的时候，我们称最终转移过来的状态为决策点。 而对于斜率优化和WQS带权二分都是利用凸包和切线的概念来优化DP [!WARNING] 斜率优化和WQS带权二分几乎完全不同，请不要混淆！ 2.凸包与切线 2.1 凸包 凸包是什么呢？其实就是字面意思，一个凸起的小包，但是这个是描述图形的。如下图： 严谨来说，应当是其图形的切线斜率是具有单调性，其导函数f′(x)f'(x)f′(x)具有单调性。 但是在OI中一般凸包都不是光滑的，如下图。 但是也还是可以满足定义的即： 经过相邻两点的直线斜率有单调性 2.2 切线与一次函数 2.2.1 一次函数 y=kx+by=kx+b y=kx+b kkk：斜率 bbb：截距（yyy 轴交点） 2.2.2 切线 对于切线来说，不阐述概念，但是我们可以观察一下性质。 我们让一个固定斜率kkk的直线取切这个二次函数（也是个凸包） 发现什么？当恰好在切点时，截距bbb 最大，这是条基本也是条很重要的性质。 3. 斜率优化 3.1 k与x同单调 来做DP题。 nnn 个任务排...