Prime
prime 模板 /* S:当前已经在联通块中的所有点的集合 1. dist[i] = inf 2. for n 次 t<-S外离S最近的点 利用t更新S外点到S的距离 st[t] = true n次迭代之后所有点都已加入到S中 联系：Dijkstra算…
Category: 笔记
ST表
ST表 原理 首先声明几点： st[i][j]表示这段区间上从第i个位置自己开始起，往后数2^i个数之间的最大值 lg[i]表示不超过i的最大2次幂指数（就是2的i次方不超过i且i尽量大） 输出RMQ最值的时候，最好用函数来写 第一部分：输入并预处理lg数组 …
字符串哈希
核心思想 将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果 模板 typedef unsigned long long ULL;…
线段树
概念 线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。 线段树可以在O(log N)的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。 操作 定义树 pushdown pushup build modify …
高精度除法
#include <iostream> #include <vector> #include <algorithm> using namespace std; vector<int> div(vector<…
高精度减法
#include <iostream> #include <vector> using namespace std; bool cmp(vector<int> &A, vector<int> &B…
MySQL笔记
基础篇 通用语法及分类 DDL: 数据定义语言，用来定义数据库对象（数据库、表、字段） DML: 数据操作语言，用来对数据库表中的数据进行增删改 DQL: 数据查询语言，用来查询数据库中表的记录 DCL: 数据控制语言，用来创建数据库用户、控制数据库的控制权限…
Trie树
int son[N][26], cnt[N], idx; // 0号点既是根节点，又是空节点 // son[][]存储树中每个节点的子节点 // cnt[]存储以每个节点结尾的单词数量 // 插入一个字符串 void insert(char *str) { i…
KMP
参考文章 文章链接 模板代码 // s[]是长文本，p[]是模式串，n是s的长度，m是p的长度 求模式串的Next数组： for (int i = 2, j = 0; i <= m; i ++ ) { while (j && p[i] !…
二分
整数二分 bool check(int x) {/* ... */} // 检查x是否满足某种性质 // 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用： int bsearch_1(int l, int r) { while (l …