wjyppm's Blog

1.Manacher马拉车算法介绍 Manacher算法，又称马拉车算法。用于计算字符串每一个位置为对称中心的回文串长度，即可以用来查询一个长度为nnn的最长回文字串。他的时间复杂度是O(n)O(n)O(n)。是该情景中效率最高的（你不遍历整个字符串咋求出来） 回文串就是从头读到尾部和从尾部读到头都一样的字符串，例如“abbba”。一个回文串是镜像对称的，也就是说他反转之后也是和原串相同的，我们就是依靠这个性质来跑出马拉车算法的。 回文串有两种，一种是奇数的串，就是字符个数有奇数个。一种是偶数的串，例如“abba”就是一个。对于奇数的传，我们可以发现他的对称中心就是中间的‘b’，但是偶数的串呢。他就有2个对称中心，一个是第二个字符‘b’，一个是第三个字符‘b’（门前有两颗树，一颗是B树，另一个也是B树） 总之偶数的回文串对称中心有2个。 2.暴力法求解 不是说讲马拉车吗？怎么先给我讲暴力法啦？ 其实马拉车就是暴力法的改进。所以我们先讲讲暴力法如何求解。 我会枚举！，每次选一个点让后判断是不是回文串！ O(n3)O(n^3)O(n3) 我会优化！我们考虑到上述加粗的，一个回文串...

1.概念与代码 1.0导入 树状数组是一种支持 单点修改 和 区间查询 的，代码量小的数据结构。利用数的二进制特性进行检索的一种树状的结构 显然可得树状数组是多叉树 如图，我们对 t[7]t[7]t[7] 进行检索 查询的过程就是每次去掉最后的二进制位的1，例如我们对7进行前缀和求值。sum(7)=t[7]+t[6]+t[4] 7的二进制是111 去掉最后的1，得110 即6 去掉6的二进制最后一个1，即100，即4 显然4不能再去1了，再去1就是0了 接下来进行维护（加），维护的过程就是每次在二进制的最后的1再加1.例如更新了a3a_3a3​ 就要修改t[3]t[3]t[3]，t[4]t[4]t[4]，t[8]t[8]t[8] 3的二进制是11，在最后的1加上1就是100 即4，更新 4的二进制是100，在最后的1加上1就是1000，即8，更新 8的二进制再加就超范围了，这时停止 显然这里有一个关键问题，如何找到二进制1，就是lowbit 1.1 lowbit 这里先给出代码 123int lowbit(int x){ return x &...

1.树上差分概念 树上差分，字面意思就是在树上做差分。 所以她能干啥能，举个例子，如果题目问经过树上某个点或某个边的次数，树上差分就可以派上用场啦。 树上差分就是利用差分的性质，前缀和的思想。只对树上一部分节点进行修改。而不是暴力全改，能将O(n)O(n)O(n)的修改降为O(1)O(1)O(1) 这个在日后会经常用到，要好好学习。 2.点差分 咱们一个一个加肯定包会TLE的，但是我们在讲树上差分啊！ 那么我们如何进行差分呢，差分是在一条链上的在树上怎么操作呢？唉！就是将树拆成链 如下 对路径3→63\rightarrow 63→6路径进行加一的操作我们先找到3和6的LCA即2，将这个路径转化为2条链，一个是2→32\rightarrow 32→3和5→65\rightarrow 65→6，如下 让后分别进行差分，红色和橙色对应上面的链 等会，为什么非要是5→65\rightarrow 65→6而不是2→62\rightarrow 62→6呢？因为2→32\rightarrow 32→3的路径已经将2已经加过了啊。 为什么我们用LCA呢，我们假设2种情况，第一种情况就...

点分治 点分治，又称淀粉质，淀粉脂。是用来解决树上路径问题。 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进...