tricks

对一个凸包和一个普通数组做卷积

根据决策单调性的知识，我们需要根据卷积和凸包的方向是否相同，来利用四边形不等式（分治）或反四边形不等式（二分栈）来优化该过程，时间复杂度 $\mathcal O(n\log n)$。

gcd/lcm + 修改询问

解决序列上的 $\gcd$ 问题的时候通常用 st 表 + 每个点向右 $\log$ 段区间的技巧。

事实上这个过程是可以带修的，线段树两个区间合并的时候左区间的右后缀只有 $\log$ 段，右区间的左后缀也是，暴力合并求新的段即可。

见过这个技巧三次了，以后遇到不要想不起来了。

prufer序列

$n$ 个点，形成了大小为 $a_{i=1}^m$ 的 $m$ 个连通块，则继续连边形成生成树的方案树是 $n^{m-2}\prod a_i$。

需要特判 $m=1$ 时 $n^{-1}$ 的情况。

前缀加正数全局 min

可以发现如果一个数比后面的数大那这个数就没用了，所以我们维护若干段数，每段数只有最后一个是有用的。

可以维护差分序列（即本段与上一段的最小值差），这样处理前缀加的时候只需要改 $b_1$ 和 $b_v$，如果 $b_v\le 0$ 那么合到上一段中去，注意我们时刻维护的是本段与上段的最小值的差，所以合进去的时候整个段的最小值与上一段的差值需要加上这个差（把最小值记在段首）。

void add(int x,int val) {
    b[1]+=val;b[x=find(x+1)]-=val;
    while(b[x]<=0) {
        b[find(x-1)]+=b[x];
        x=f[x]=find(x-1);
    }
}
int Min(int x) {return b[1];}

笛卡尔树到括号序双射。

递归结构，括号内放左儿子，括号外放右儿子。

矩阵每行是一个区间，求积和式 $\bmod \ 2$。

行列式的性质允许我们对列差分，这样每行最多剩两个值（若 $r=n$ 则只剩一个值），把两个值连边，只需判断图是否为自环树森林即可，有 $\ge 2$ 的环就寄。

数据结构技巧：带 down 的主席树

每次 push_down 时，若该点有标记，显然我们必须复制两个儿子，若该点无标记，则我们只需复制我们需要递归的儿子。

最小节点数的写法是，有标记则复制两个儿子，然后将这两个节点设为特殊的，若我们递归到特殊的节点则不复制它，每次递归前清空特殊标记。

wqs 二分上界

虽然我们有可能分 $n$ 段，但我们不应认为二分上界 $\times \ n$ 会爆 long long 就开 __int128，我们只要保证存在一个合法方案的权值 $\le \infty+R$，那么我们就可以把二分上界设为 $R$，把初值设为 $\infty$。

这是因为我们的分段是一个一个 $k$ 加上去的，不优的显然会被及时扔掉。

树哈希

对于每个深度我们随一个值 $x$，并维护 $f_u=\prod_{v\in son_u}(x_{h(u)}+f_v)$，$h(u)$ 是高度，可以证明将其视为关于 $x$ 的多元多项式时两棵有根树相同等价于多项式相同。

前后缀二分图完美匹配计数

问题形式：左右各 $n$ 个点的二分图，左边每个元素连的是一共前缀或者一个后缀，对完美匹配计数。

只有前缀我们都知道怎么做，从左往右扫，维护当前前缀可选的数的个数 $x$，然后遇到一个前缀就选一下，把答案乘上 $x$，而后 $x\gets x-1$。

有后缀，我们使用容斥原理，差分成全局 - 前缀，由于一个后缀可能选全局，也可能选前缀，我们需要额外记录。

从左到右，设 $f_{i,j}$ 表示前 $i$ 个元素考虑完了，发生匹配了 $j$ 个，带容斥系数的贡献和。

扫到一个前缀我们就直接选，系数是 $f_{i,j}(i-j)\to f_{i,j+1}$。

扫到一个后缀我们就分讨，如果它选全局，就什么也不做，最后再给它分配，如果它选前缀，$-f_{i,j}(i-j)\to f_{i,j+1}$。

前进一步，把 $i$ 增加 $1$ 即可。

最后 $f_j$ 的贡献是 $(n-j)!$。

树上邻域数点

最简单的例子：求邻域内点的个数。

使用点分治，sol(int x,vec<int> v) 表示点分治子树是 $x$，需要处理的点集是 $v$。

求解时，询问点恰好在 $x$ 的一个子树 $r$ 内，也就是求出其他子树中距离 $x$ 为定值的点数，再减掉 $r$ 子树内算错的贡献即可。

数点是类似的，邻域一维是可以被树分治掉的。

多项式卷积阶梯分治

$\binom{i+j}if_i\to g_j$ 怎么卷？

构造 $F_{n-i}=\frac{f_i}{i!},G_{i+j}=(i+j)!$，取 $F*G$ 把前 $n$ 位删掉，然后每位除 $j!$ 即可。