Doraemon's Blog

可持久并查集 前置知识：主席树、可持久化数组 作用：保存历史的集合版本，查询过去版本 空间复杂度>=(klog(n)+2^log(n)^-1) [一般开40倍原空间] 详细讲解 大致过程将fa数组和dep数组可持久化，fa数组就有了各个版本不同的值，如果开结构体的话只需要将fa定义成结构体类型，因为两个数组可持久化后下标是相同的，需要注意的是不能路径压缩，一定要按秩合并！ 题目洛谷模板 题意给定n个集合，每一个集合初始只有自己一个数，接下来m次操作，每次操作有三种选择，合并a和b，回到k版本，询问a和b是否属于一个集合 解法将fa数组和dep数组可持久化，需要注意的是一定不能路径压缩，因为每次要保存版本，只是拉出来一条链，压缩路径的话就会影响其他版本的fa数组值，例如现在高版本压缩了一次路径，低版本的fa数组值被改变了，之后查询低版本时就会出错！如果没有了路径压缩那么时间就会慢很多，所以一定要按秩合并来优化一下，为什么按秩合并会快一点呢？ 看这个图，倘若询问2和4是否在一个集合，第一个畸形图就需要多往上走两步，而第二个图就可以省下些时间。 CODE1234567891011 ...

可持久化数组(可持久化线段树) 前置知识：主席树 作用：记录下历史版本，可以进入历史版本进行修改或者查询 洛谷P3919 题意给定初始版本数组的n个数，之后m次操作，可以查询或者单点修改，每次查询或者修改都会产生一个新版本，查询产生一摸一样的版本，修改会产生一个只有一个位置不同的版本，版本数连续递增，输出每次查询某一个版本的某一个位置的数是几？ 解法原本想用vector开n个表示数组的每一个位置的不同版本，想的是每次只把一个数塞进要修改的ve里，不过这样会有问题。正解是可持续化数组，本质上就是一个保存历史版本的线段树，利用主席树的思想单点修改时只拉出来一条链保存修改过的信息。 CODE123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#include <bits/stdc++.h>//#pragma G++ optimize(2)//#pragma G++ optim ...

计算几何皮克定理： 2S=2a+b-2 (S:三角形面积，a三角形内部点的个数，b三角形边上点的个数)，求三角形内点的个数 求线段上整数点的个数：gcd(abs(x2-x1),abs(y2-y1))+1 判断一个点是否在多变形内部：以这个点向多边形顶点做向量，相邻两两做叉积(左乘右)，若得出的所有结果符号都一样，则在内部 计算多边形面积：从原点向多边形顶点做向量，相邻向量做叉积（右乘左）累加求和除以2 判断一个点是否在两条直线中间：从两个直线上随便找两个点，从当前点向交点和直线上一点做向量，两向量做叉乘，另外一条直线也是如此，叉乘的两个结果如果符号不同就在中间，否则不在

ICPC训练赛-Philosopher‘s Walk题意 如图所示，给定这样的一个n阶图形，每次从左下角开始走，问走了m步后的位置坐标？ 这个图是有规律可循的，定义f(i)是i阶图的样子，那么f(i+1)就是四个f(i)拼成的，上面两个和f(i)一样，左下角是f(i)顺时针旋转90度得到，右下角是f(i)逆时针旋转90度得到，因此可以定一个dfs函数返回的是坐标，不管这个图形是否旋转，我们只求这个图形没有旋转，也就是正着放时走m步的坐标，即使它旋转了，这个坐标也只不过是换了一个角度而已，我们是知道图形的尺寸的，那就可以根据这个尺寸来推出这个点的坐标 CODE123456789101112131415161718192021222324252627282930313233343536#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<int,int> pii;const int N=100010;int n,m; pii dfs(int x){ if( ...

主席树(可持续化权值线段树) 可持续化系列的一种数据结构，可以保存修改的版本，本质上是一种可持续化权值线段树 区间第k小倘若不是区间，而是每次求所有值的第k小，一个权值线段树就搞定了，将所有数离散化一下，将数值作为插入位置建树，之后查询第k小时，如果左子树插入点数量大于k就在右子树上，否则就在左子树上，这样就能第k小的数在排好序的数组中排第几个了，每次修改花费logn时间，查询也花费logn时间 而如果现在变成了区间第k小，单纯的线段树就维护不了了，因为无法保存过去的信息，如果可以保存过去没有修改过的信息就好了，（每次修改都建一颗新树，空间炸不炸呀），其实容易想到修改一个点后，变动的点只是这个点的所有祖宗节点（包括父亲节点），只有logn个（n个点的树深度最多是logn），所以可以拉出来一条链来保存修改过的信息 如图，红色的链就是修改过的信息 主席树因为要保存版本信息，无法用2*id表示左孩子那种方式建树，要用朴素的lson和rson数组表示左右孩子 个人理解主席树本质就是前缀权值线段树，权值线段树保存的是每一个区间的值的个数，而主席树就是对每一个前缀都建了一棵树，只不过是优化了 ...

马拉车算法(Manacher):::success 解决的问题： 以O(n)时间求出一个字符串的最长回文子串长度 ::: 算法流程如果求最大回文子串，暴力做法是从一个点开始，每次向左和右同时延伸一个单位，比较是否相同，但是这种方式比较难受的是如果字符串长度是偶数，那么可能对称中心不在字符上，而在两个字符之间，如果还想使用上面的方法就必须让指针在字符之间停留一下，所以考虑在每一个字符之间以及开头结尾（开头结尾添加是要让添加字符后的答案和未添加时的答案有一个对应关系）都添加相同的未出现的字符，这里用”#”表示，这样一来aba就变成了#a#b#a#，这样一来无论原串的长度为奇或偶转化后的字符串长度永远是奇数(2*l+1)，这时会发现添加后的字符串找出来的最长回文子串长度永远等于原串的最长回文子串长度+1（无论原串长度为奇数或偶数），所以对改变后的字符串求解的答案-1就是答案。 引入Len数组表示一个字符向左或向右可延伸的最长回文长度，比如aba，那么Len[1]=2（ab） 当求Len[i]时Len[i_mirror]是已知的，又因为黑色区域都是回文的，所以Len[i]=min(Len[i ...

扩展KMP 解决的问题： 求解母串以i位置开始的后缀子串与模式串的最大公共前缀 时复： O(母串长度+模式串长度) 引入两个概念，extend[]数组表示以母串i位置开始的后缀子串与模式串的最大公共前缀，next[]数组表示模式串以i位置开始的后缀子串与模式串的最大公共前缀，一个是模式串与母串，一个是模式串与模式串 与KMP类似，都采用了利用之前已经得到的信息来优化当前的时间 大致过程记一个po表示起始位置，求解extend数组需要先求出next数组，而求解next数组的过程和求extend过程一致，只不过是把模式串当作母串 (1) 第一步，我们先对原串S1和模式串S2进行逐一匹配，直到发生不配对的情况。我们可以看到，S1[0]=S2[0],S1[1]=S2[1],S1[2]=S2[2],S1[3] ≠S2[3],此时匹配失败，第一步结束，我们得到S1[0,2]=S2[0,2],即extend[0]=3; (2) Extend[0]的计算如第一步所示，那么extend[1]的计算是否也要从原串S1的1位置，模式串的0位置开始进行逐一匹配呢？扩展KMP优化的便是这个过程。从exten ...

树链剖分 求解问题：在树上进行区间修改区间查询问题，求lca问题，维护路径信息 主要思想：将树上的点分割成一条一条的链，每一条链的第一个点是链头(父亲)，利用dfs序按照链优先的思想加上序号，这样每一条链上面的序号都是连续的，就把树上的点映射到了一条数轴上 时复：找到父亲，重子节点，子树大小（dfs1）O(N)，进行一次dfs序(dfs2 O(N))，每一条路径都能被分割成最多log2n条链，因此链头数量不超过log2n，每次求lca时复logn 重链剖分 dfn数组: 每一个点映射到链上的标号 rnk数组: 每一个标号对应点的编号 (rnk[dfn[x]]=x) dep数组: 每一个节点的深度 fa数组: 节点父亲 siz数组: 子树大小 son数组: 重孩子 top数组: 节点在链上链头的编号 以上7个数组是树链剖分的几个必要数组，根据题目不同会使用上面的某几个数组 定义： 重子节点是子树节点最多的那棵树的根节点，如果有多个随意取出一个即可 剩下的非重子节点的点都是轻子节点 从当前节点到重子节点的边是重边 从当前节点到轻子节点的边是轻边 若干条首尾相连的重边称为重链，所有落单 ...

题目 题意从(1,1)出发走到(n,m)，途中有墙有门有钥匙，问最短几步走到右下角。 思路利用状态压缩，用二进制位表示第几种钥匙是否持有，利用BFS爆搜，再开一个数组储存状态来记忆化剪枝 实现方法有很多种，可以利用邻接表建边，可以直接利用Next数组表示下一个位置，邻接表利用空间换取了时间，表示墙和门时如果不用邻接表，则需要用map

题目 题意如图所示，旋转最少的电线使得左面的电源和发光器相连、 思路考虑把所有电线已经相连的点设为边权为0，没有连接的，比如电线是主对角线，副对角线上的两个点就应该设为边权为1，最后跑一个从左上角到右下角的最短路径，将每一个点映射到一维数组中。 dijstla当然可以做，但是双端队列更高，因为这个图中只有边权为0和1的点，可以把优先队列的log(n)省掉，当遇到边权为0的点时就把点直接添加到队头，遇到边权为1的点放到队尾，并且判断能否更新当前点离起点的距离。 CODE123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113#include <bits/stdc++.h>#de ...