用来记录一些不属于正统算法，但是是一些常见的经典套路的技巧。科技？
记录的东西会有点 naive。
以及一些简单的结论。（但是看起来简单，用起来惊为天人）
分块时间换空间
牛了，常见套路，一般用分块来用时间换空间。
求一个可修改序列中 \([l,r]\) 区间内不连续取 \(3\) 个数的所取的数最大和是多少。
\(n\le 1.2\times 10^6\)，\(m\le 2^{18}+5\)。
时间限制：2s
空间限制：32MB
如果是朴素的 dp，大家都会。
如果我们考虑修改和区间询问，那么大家都会 DDP。
但是发现空间完全开不下。
空间：int 开 8 个 1e6 的数组，long long 开 4 个。
这时候，对原数列分块，然后块间建线段树，然后块内暴力构造矩阵和求解。虽然会慢一点，但是最终空间是够的，时间也能过去。
前缀优化建图
一种优化时空的建图方式。我们考虑如果每次要求一个点对一堆点连边，除了线段树优化建图以外，可以考虑是否可以用前缀优化建图。
比如说在 2-sat 中的前缀优化建图：
给 \(n\) 个点，分成 \(k\) 部分，\(m\) 条限制表示两个点至少选一个，每部分恰选一个。求有无可行选法。
一般我们会把一个点拆成两个，表示选或者不选。现在我们拆成 \(4\) 个，表示选或者不选，以及前缀中是否有选，后缀中（不包括本身）是否有选。
这样一来，我们对一堆点连边就变成了向一个点连边，那么对于一堆的点，我们需要预先连一些边。
- 如果一个点选了，那么它前缀中肯定有选了；
- 如果后缀 \(i\) 有选，那么 \(i\) 这个点不能选（同一堆中不能一起选）；
- 如果前缀 \(i\) 有选，那么前缀 \(i+1\) 有选；
- 如果后缀 \(i+1\) 有选，那么后缀 \(i\) 有选；
- 如果 \(i\) 选了，那么 \(i-1\) 的后缀选了；
- 如果前缀 \(i\) 有选，那么 \(i+1\) 不选（后面的点交给前缀 \(i+1\)）。
这样会得到这样的图：
然后直接连边就可以了。
或者考虑网络流的优化，具体见这题。
O(logn) 分解质因子
众所周知每个数都只有 \(\log n\) 级别的质因子。那么的话我们可以利用线性筛每个数都是用它的最小质因子筛掉的，记录一下，然后分解的时候每次除以这个最小质因子就可以精准获取质因子，也就是 \(O(\log n)\) 分解了。
斐波那契前缀和公式
太神奇了，二次以上也是有公式的。
C++ 语法
求一个数组中连续区间的最值：
*max_element(a+l,a+r+1)
向上取整的数论分块
你可以这样：
然后就变成向下取整的数论分块了。
代替弱化的平衡树的堆
还是来记一下。用来解决加入，删除，查询最值。可以用极短的代码来代替平衡树。你搞两个堆，我们叫做 \(A\) 和 \(B\) 吧，每次插入的时候，把元素压到 \(A\) 中，然后删除就压到 \(B\) 中。每次查询最值的时候就比较 \(A\) 和 \(B\) 的堆顶是否相同，如果相同就同时弹掉，否则就返回 \(A\) 的堆顶就是当前询问的最值了。
struct Heap{
priority<int> A,B;
void ins(int x){A.push(x);}
void del(int x){B.push(x);}
int ask(int x){
while(!A.empty()&&!B.empty()&&A.top()==B.top())
A.pop(),B.pop();
if(A.empty()) return -1;
return A.top();
}
};