静态主席树

MayFlyyh | 学习笔记 | 2018-06-16
## 静态主席树 维护区间查某个数的存在次数或者第k大以及更多 可持久化线段树+权值线段树 可持久化线段树,每次修改logn个节点包含当前需要修改的点x的区间,从前一个中继承剩下无需修改的区间 主席树查询:用区间下标root[r]-区间下标root[l-1]的结果查询 比如一个数在r以内的出现次数为x,在l-1以内的出现次数为y 那么在l-r区间内... [阅读全文]

Splay 学习笔记(未完成)

MayFlyyh | Splay, 学习笔记 | 2018-05-06
一个月没写博客了,今后要更加努力啊 Splay Tree 是一种二叉排序树 通过不断旋转以维护单词操作复杂度为log(n)级别 ![Main](http://t1.aixinxi.net/o_1ccqap2hip581p97uahtuqu9ha.png-j.jpg) 在这里讲述的操作有:插入,删除,查询第k大,rank,前驱后继 旋转分三种情况 1.Zig ![Zig](http://t1.aixinxi.net/o_1ccqaqirpt7kmkki3i1... [阅读全文]

题解 LuoGu P4147 玉蟾宫 最大子矩阵问题 悬线法 学习笔记

MayFlyyh | DP, 学习笔记 | 2018-03-10
### 题解 LuoGu P4147 玉蟾宫 最大子矩阵问题 悬线法 学习笔记 > 题目描述 > 这片土地被分成N*M个格子,每个格子里写着'R'或者'F',R代表这块土地被赐予了rainbow,F代表这块土地被赐予了freda。 > 现在freda要在这里卖萌。。。它要找一块矩形土地,要求这片土地都标着'F'并且面积最大。 > 但是rainbow和freda的OI水平都弱爆了,找不出这... [阅读全文]

线段树学习笔记

MayFlyyh | 学习笔记, 线段树 | 2018-02-24
线段树学习笔记 已知一个数列,你需要进行下面两种操作 1.将某区间每一个数加上x 2.求出某区间每一个数的和 线段树,即是将一个整区间分解成几小区间,保存多个子区间值以便查询时节约时间的数据结构。而LazyTag的设置使在单点修改节约了时间。 L1 1-10(1) / ... [阅读全文]

LCA学习笔记

MayFlyyh | LCA, 学习笔记, 未分类 | 2018-02-13
建树 结点数为N 边数为M 根节点S log2N 为树的最大深度 int log2N=log(1.0*N)/log(2.0)+0.5; 通过DFS预处理出树与深度 inline void dfs(int x,int f){ V[x]=1; D[x]=D[f]+1; F[X][0]=f; for(int i=Last[x];i;i=e[i].next){ if(V[x]) continue; dfs(e[i].to,x); } } 朴素算法 DFS... [阅读全文]

最短路学习笔记

MayFlyyh | 学习笔记, 最短路 | 2018-02-13
图的存储 邻接矩阵 初始化 G[i][j]=inf G[i][j] = v 表示 从点i与点j有边,权值为v; 有向图存一遍,无向图存两遍,重边取最小(吧) 适用于稠密图 领接表 定义一个Last[N]数组用于存储某点最新连接的边号 int Last [N],cnt = 0; struct Edge{ int to,v,next; } E[M] ; 加边: inline void ... [阅读全文]
Ɣ回顶部