trick 总结
听取MLE声一片
·
·
个人记录
主要思想：
序列上问题不会做就试试分治。
计数的精髓是通过强令细化状态或升维使统计不重不漏。
数据结构的精髓是规约到已有模型，本质是合并重复信息。
高复杂度优化到低复杂度要通过调整找出所谓单次 O(1) 或 O(\log) 的量。
无法动态查询的情况离线后动态维护当前状态。
尤其考虑操作顺序先后对答案有无影响。
只允许尾部撤销可以用线段树分治维护。
尾部撤销可以用线段树分治维护。
位置无影响则可以使用带修莫队以及撤销 dp 等等。
无顺序影响的可以考虑扫描线思想动态维护当前状态。
很多情况下多组询问都是离线后动态维护信息来降维。
有向图正图难做考虑建反图。
写 dp 前先考虑优化状态。
最大化一个集合的最小值考虑从大到小类扫描线。
区间翻转排列会增多至多四个不连续位置。
树上路径可以拆分为深度相减。
状态数不多可以尝试直接搜。
传递闭包尝试 bitset。
如果要求一个最优状态，而一个劣状态可以由一个优状态到达时，尝试使用二分。
根号分治，小段暴力，大段标记。
容斥时一些状态可以由另外一些状态一一对应转移过来（CF348D）。
bitset 优化合法性 01 背包并记录状态（CF356D）。
树上一个点集的最小连通子图是按照 dfn 序排序以后相邻点的距离之和（CF372D）。
以一个点为起点画一条不经过多边形端点的射线，若和多边形的边有奇数个交点则其在多边形内部，偶数个则在外部。方向只有两个的情况下把区间视为上开下闭（CF375C）。
不能取到的东西权值可以赋为 -inf（CF375C）。
类走迷宫类的题可以多开一维表示最短走了多少步（CF375C）。
精度要求较低的情况下求凸包面积可以直接积分启动（CF379E）。
事先定义出全局变量要比多次定义局部变量快（CF379E）。
答案为浮点数的时候 \frac{1}{2^k} 类贡献在 k 较大时可以忽略（CF380E）。
子集求和使用高维前缀和（CF383E）。
对于一个线性基的每一位，如果它是某个基的最高位，则只有那一个基的这一位为 1 ，反之任何最高位大于这一位的基的这一位可以为任意数（CF388D）。
区间加组合数，是 len+1 阶差分进行单点修改（CF407C）。
A->B->C->D 类统计直接做为 n^4，可以做预处理 (A->B->C) 然后再做 A->(A->B->C)->D（CF416E）。
网格图（对角线）染四种颜色且每条边连的顶点颜色不同，合法方案当且仅当奇数行 121212，偶数行 343434。
多边形问题考虑区间 dp。
字符串匹配考虑根号分治（CF444D）。
图上路径最小值类问题考虑排序后从小到大依次取（CF444E）。
最大公因数大于一的最大匹配个数，从大到小枚举素数和倍数匹配，剩下的把 2p 留下，因为 2 的倍数出现的次数最多，要把贡献都留给 2（CF449C）。
判断排列是否存在长度为 3 的子序列为等差数列，可以转化为求中间位置的数向两边拓展的是否是一个回文串（CF452F）。
计数问题转化考虑「一一对应」（CF40E）。
构造题尝试整体移动加上同一个变化量（CF468C）。
图的问题如果环内的贡献可以简单求出考虑缩点（CF475E）。
随机数树高为根号。
给定 $n$ 条直线求凸壳，可以从当前点二分找出第一个优于此直线上的位置，然后跳过去，可以在 $O(n^2\log n)$ 的时间复杂度内简单的遍历凸壳。
结构体一定要清空。
DAG 的拓扑排序中，任意时刻在队列里的点都不可互相到达（CF1062F）。
矩阵快速幂首先顺序要 $i,j,k$ ，其次要取模优化（一个位置开 `ull` 每若干次取模），如果模 $10^9+7$ 可以累计 $18$ 次再取模。
树上有 $O(n)$ 次基于原树的一个端点固定的链修改，每个链修改都要查询树上信息，但每个修改都至少要对链上的每个点修改。可以从把所有修改离线，固定的端点开始 dfs，通过插入、撤销动态维护树的形态。
$x$ 是 $lowbit(x)$ 的倍数。
有结合律的东西就可以快速幂。
整体二分（CF484E）。
序列上有若干个区间，区间不交错（包含或无交），则这些区间可以构成一棵树（CF494C）。
树上计数 dp，$f_u$ 表示子树内答案时，若所求为连通块，则令 $f_u$ 的答案强制和 $u$ 连通，$u$ 到父亲强制不选。
树上高斯消元，从叶子往上消元，再从根节点已知答案向下求解，时间复杂度可以做到 $O(n)$ 或 $O(n^2)$。
期望题可以不解方程，只求出要求东西的系数和常数项。
[双栈](https://www.luogu.com.cn/blog/adfgas/fou-dai-shan-di-chi-qu)，可以合并区间的不带删尺取。核心思想是枚举中间点然后左右拼区间，处理完后中间点直接跳到右区间。
题面未规定根时可以随机一个点为根避免被卡。
环上最大流，断边权最小的边并把剩余环上每条边都加上最小边权，最大流即为链上最小值。
$O(n\log n)-O(1)$ [st表](https://www.luogu.com.cn/blog/AlexWei/leng-men-ke-ji-dfs-xu-qiu-lca)。
数据比模数大先取模。
几个 $10^{18}$ 级别的数可以先加起来再取模。
栈模拟递归可以用当前弧优化。
维护括号序列可以上树，树也可以转化为括号序列。
直接维护很困难但递推关系很简单可以使用矩阵乘法，带撤销也可以线段树维护矩阵乘法。
多个数组成约束条件考虑中间数作为关键（P3722）。
两部分组合考虑枚举中间分割线。
给定若干个区间，去除被完全包含的区间，剩余区间按左端点从小到大排序后，其右端点也为升序。
块内离散化效率严重依赖于内存访问连续。
可以假定答案是一个前/后缀。
询问总和不超过一个范围可以使用根号分治。
dfn 序中位数一定在重心的子树内。
$\min(A,B)=A+B-\max(A,B)$。
换根 dp 可以使用分治来避免撤销。
$x \oplus y \oplus z=k$ 等价于 $(x\oplus k)\oplus(y\oplus k)=z\oplus k$，来把形式化为相同的。
区间取交，交一定是一个区间，可以枚举交的区间的左端点。
uset 远快于 umap。
dfs 树没有横叉边。
求多项式的整数根，利用因式定理，只有常数项的因数可能会成为答案。
连通块数等于点数减边数。