mygr main()

题单：# LXL的支配对题单 常见于找一个点对计算答案的问题 当我们拥有若干个点对时，我们可以考虑点对间的 “支配” 关系，即对于两个点对 $A,B$ ，选择 $A$ 是否一定比选择 $B$ 更优(贡献更大，可选范围为其的子集)，将问题转化为支配对的包含问题 常见的剔除方式有： # P7880 Ynoi2006 rldcot，由于被包含的区间一定比其本身更优，因此剔除被包含的部分，支配点对数量与启发式合并相同，因此暴力维护即可 [[二进制#^8ecb0b | MINXORSEG]] ，利用前缀二进制的支配对只有 $logn$ 条 # 背包，将被包含且长度小于 $r-l$ 的部分删去，因为其无论如何都没有左右两个决策更优

关于下取整： 当题目中存在向下取整的除法不好处理时，可以考虑反过来做，用一个区间的数的乘法来表示 # MRO-Ant colony-蚂蚁窝 摩尔投票法： 相关链接：[[绝对众数]] 普通幂转下降幂 $$x^n=\sum_{i=0}^{n} {n\brace i}x^{\underline i} $$ 曼哈顿距离转切比雪夫距离 $$\max{ a,b }=\mid \frac{a+b}{2} \mid + \mid \frac{a-b}{2} \mid$$ 值域相关 当遇见跟数的值域相关的题目时(排列，1e6，质数乘积，两数相加取模)，考虑将数通过拆分分为大小两部分，可能会产生若干关于匹配的性质 例如 [[质数相关#^372880 |卡牌]] ，# Extreme Permutations,# Ehab’s REAL Number Theory Problem

总题单 # 何为数据结构 # 何为数据结构二代目 [[线段树]]： [[平衡树]]： [[分块]]： [[笛卡尔树]]： [[扫描线]]： [[堆]]： [[Trie]]： [[模拟费用流]]： [[RMQ问题]]： [[KD-Tree]] [[单调队列-单调栈]] 综合模型/典型题析 [[函数复合问题]] [[区间的序列区间查询]] [[论区间覆盖的暴力退标记]] [[支配对]]： #important

# 数学全家桶 [[质数相关]]： [[斜率]]： [[拉格朗日插值]]： [[组合数学]]： [[概率与期望]]： [[异或]]： [[矩阵乘法]]： [[卡特兰数]]： [[反射容斥]]： [[BSET定理]]： [[矩阵树定理]]： [[数学相关Trick]]： [[多项式]]： [[复杂度证明]]： #important

相关链接：[[计算几何]]，[[凸包]]，[[斜率优化]]，[[数论]]，[[李超线段树]] Trick $$等差数列 \Rightarrow 李超树 \Rightarrow 斜率优化(凸包)$$

[[mygr的日记]]： #structrue

Trick 对于一个图 $G$ ，将其分割为若干个点集使得 $S_1 \cup S_2 … \cup S_n=G$ ，对其中的每个 $S$ 求解出最小生成森林 ，删去非最小生成森林的边，再对 $S_1,S_2,S_3$ 这个整体求解出最小生成树，就能得到 $G$ 的最小生成树，配合一些奇奇怪怪的分治算法即可，# AT_cf17_final_j Tree MST

Trick 用 spfa 判断负环时，有两种判断方式： 判断某个点的 松弛 次数 判断某个点的最短路长度 常用于 [[差分约束]]

[[折半搜索]]： [[异或]]： [[二分答案]]： [[启发式合并]]： [[STD]]： [[随机化]]： Trick

致永远的SP李超线段树 李超线段树也可以用于维护 全局点最值，达到类似于堆的效果，用于最短路