github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

树上每个子树的信息：子树大小，DFS 序（从 1 开始） 这样的话 [o.dfn, o.dfn+o.size-1] 就表示一颗子树，方便用树状数组/线段树维护 模板题 https://ac.nowcoder.com/acm/contest/6383/B 例题 https://codeforces.c

github.com/EndlessCheng/codeforces-go

有多少个（编号）不同的模式串在文本串 text 里出现过

github.com/EndlessCheng/codeforces-go

原题 https://codeforces.com/problemset/problem/1215/D github.com/EndlessCheng/codeforces-go

O(n) 做法，计算每个数的贡献： 对于一个数 a[i]，若其出现在一个长度为奇数的子数组中 则有两种情况：a[i] 左右均有奇数个数，或左右均有偶数个数

github.com/EndlessCheng/codeforces-go

前缀最大值+后缀最小值 github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

LC 834 返回一个表示节点 i 与其他所有节点距离之和的列表 ans

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

点 a 关于直线 l 的对称点 求投影 p，然后将 ap 延长一倍

与两圆外切的圆的圆心 挑战 p.275 记圆心在 (x,y)，半径为 r 的圆为 O1， 另有一半径为 R 的圆 O，若 O 与 O1 相切， 则 O 的圆心轨迹形成了一个圆心在 (x,y)，半径为 R-r 的圆 因此，问题变成了求两个圆的交点 圆的面积并 - 两圆的特殊情形 todo https:

两圆公切线 返回每条切线在圆 o 和圆 ob 的切点 NOTE: 下面的代码是基于 int64 的，没有判断 eps

* O(n) 做法：统计小于和等于 target 的元素个数 由于排序后，相同的值是连续的，记小于 $\textit{target}$ 的元素个数为 $\textit{less}$，等于 $\textit{target}$ 的元素个数为 $\textit{equal}$，那么答案即为 $$ \t

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

* O(n) 一次遍历 根据题意，当第 $k$ 个人买完票时，在 $k$ 前面的人买的票不会超过 $\textit{tickets}[k]$，在 $k$ 后面的人买的票不会超过 $\textit{tickets}[k]-1$，累加所有购票数即为答案。 */ github.com/EndlessC

github.com/EndlessCheng/codeforces-go

负二进制转换 LC1017/周赛130B https://leetcode-cn.com/problems/convert-to-base-2/ https://leetcode-cn.com/contest/weekly-contest-130/

一般图（带权）最大匹配（带花树 Edmonds's blossom algorithm） MWM https://en.wikipedia.org/wiki/Maximum_weight_matching https://en.wikipedia.org/wiki/Blossom_algori

状压 N 皇后 LC51 https://leetcode-cn.com/problems/n-queens/ LC52 https://leetcode-cn.com/problems/n-queens-ii/

LC 52 N 皇后方案数

github.com/EndlessCheng/codeforces-go

LC 42 接雨水

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

TODO: 虚树 Virtual Tree / Auxiliary Tree https://oi-wiki.org/graph/virtual-tree/ https://www.luogu.com.cn/problem/P5891 https://class.luogu.com.cn/class

github.com/EndlessCheng/codeforces-go

转化为长度为 x 的向量

github.com/EndlessCheng/codeforces-go

bst 存的是互不相交的区间 [key,value)，现尝试删除区间 [l,r) 若不在任何区间内则返回 false，否则删除、修改或分裂区间

bst 存的是互不相交的区间 [key,value)，现尝试插入区间 [l,r) 若与已有区间重合则返回 false，否则合并或添加该区间，返回 true

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

位运算写法 github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

* 并查集 只有路径压缩的并查集复杂度是 O(nlogn) 的，这也是大多数情况下的实现方案 只有启发式合并（按深度合并）的并查集的复杂度也是 O(nlogn) 的，适用于可持久化的场景 */ 普通并查集 https://oi-wiki.org/ds/dsu/ https://cp-algorith

并查集 - 维护边权（种类） 简单易懂的讲解：https://www.bilibili.com/video/av68342657?p=2 https://cp-algorithms.com/data_structures/disjoint_set_union.html#toc-tgt-11 http

并查集 - 维护点权 维护的可以是集合的大小、最值、XOR、GCD 等 https://codeforces.com/edu/course/2/lesson/7/1/practice/contest/289390/problem/B https://codeforces.com/problemset

o=1 [l,r] 1<=l<=r<=n

一般写法是更新到当前版本，然后把返回的新版本加在 t 的末尾，即 t = append(t, t[len(t)-1].update(i, add)) 注意为了拷贝一份 pstNode，这里的接收器不是指针

* 有向图欧拉路径 本题与 [332. 重新安排行程](https://leetcode-cn.com/problems/reconstruct-itinerary/) 一样，都可以抽象成如下问题： > 给你一张有向图，在这张有向图中找到一条欧拉路径。 对于此题，由于题目保证有解，所以有向图肯

圆与扫描线 todo https://blog.csdn.net/hzj1054689699/article/details/87861808 http://openinx.github.io/2013/01/01/plane-sweep-thinking/ http://poj.org/probl

todo 计算几何三维入门 https://www.luogu.com.cn/blog/105254/ji-suan-ji-he-san-wei-ru-men

github.com/EndlessCheng/codeforces-go

*一次遍历 由于每株植物都需要浇水，所以答案至少为植物的个数。我们只需要额外计算出在哪些位置往返即可，在位置 $i$ 处往返需要走 $2i$ 步，额外加上这些步数即为答案。 */ github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

* 计算出 $\textit{nums}$ 的前缀和 $\textit{sum}$，记所有元素的和为 $\textit{tot}$。 对于不修改的情况，合法分割相当于要满足 $\textit{sum}[i] = \textit{tot}-\textit{sum}[i]$，即 $\textit{s

github.com/EndlessCheng/codeforces-go

* 统计连续相同颜色的长度 由于删除操作需要两边都有相同颜色，所以对于每一串连续相同的颜色，最边上的两个颜色是不会被删除的。 因此删除一种颜色不会对另一种颜色产生任何影响，我们只需要统计每一串连续相同颜色的长度 $l$，若 $l>2$，则可以删除 $l-2$ 个颜色。将该值按颜色分别累加，记 $

判断点 a 到线段 l 的距离 <= r，避免浮点运算

* 由于我们只关心每个字母出现次数的奇偶性，因此可以将「字母出现次数」转换成「字母出现次数的奇偶性」，这可以用一个长为 $10$ 的二进制串表示，二进制串的第 $i$ 位为 $0$ 表示第 $i$ 个小写字母出现了偶数次，为 $1$ 表示第 $i$ 个小写字母出现了奇数次。 考虑字母出现次数的前缀

LC 140

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

求矩阵的特征多项式 todo https://www.cnblogs.com/ywwyww/p/8522541.html 线性基（子集异或和问题） https://oi.men.ci/linear-basis-notes/ 模板题 https://www.luogu.com.cn/problem/P