根号分治初步
根号分治的本质就是结合两个暴力，使得复杂度得到了均摊。题目：Problem - 1207F - Codeforces现在有两种暴力，第一种是根据题目模拟，修改操作时间复杂度 $O(1)$，查询操作时间复杂度 $O\left( \…
CATEGORY
学习笔记
这个分类下的文章与记录。20 篇内容
↗
缩点与强连通分量
Kosaraju 算法求强连通分量原理遍历两次 DFS，第一次遍历的时候按后序存储到数组里面，做记录。 第二次，从后往前按之前记录的数组，遍历所有这次没有被访问的点。证明云剪贴板 - 洛谷 | 计算机科学教育新生态 (luogu…
线段树 II 之 懒惰标记
线段树 II 之 懒惰标记前置知识：线段树 I – ztr 的小窝 (ztrztr.top)懒惰标志 Lazy Tag懒惰标志，是维持线段树的区间修改查询的复杂度在 $O(\log n)$ 级别的一个方法。正常的区间修改查询的复…
初赛笔记
CSP 初赛笔记，持续更新中。出栈序列出栈序列满足 FILO 的规则，也就是先进后出。如果入栈的顺序是降序排列，那么可以快速判断的依据就是任意数A的后面比A大的数都是按照升序排列的如果入栈的顺序是升序排列，那么可以快速判断的依据…
前缀函数 & KMP 学习笔记
前缀函数前缀函数的定义是：一个字符串最长的真前缀和真后缀。真前后缀的意思是这个前缀或者后缀不是这个字符串本身。我们定义 $f(i)$ 的意思是这个字符串从第 $1$ 位到第 $i$ 位的字符串的前缀函数。通过定义，我们可以暴力求…