max、逻辑与绝对值

在诸多时候（例如组合计数），我们很方便处理加与乘，此时 $\max$ 这种东西对我们是一个头疼的东西。

同样令我们头疼的还有逻辑与、逻辑或、绝对值，这些东西在一定前提下是可以互相转化的，显然将所有形式转化到一起，有利于我们观察性质。

叙述完了目的，我们开始正文。

max 的性质

$\max(a,a)=a$ 配合上交换律结合律使得 $\max$ 是一个很有性质的运算， $+$ 对 $\max$ 还有分配律，甚至 $\min$ 对 $\max$ 也有分配律。

同向的 $\max$ 可以让我们拆掉很多东西，很典型的，倘若我们的“贡献”指的是对答案取 $\max$ ，那么 $\max(a,b)$ 贡献到答案，就不如 $a,b$ 贡献到答案。

$\max$ 运算不可逆是它唯一的缺点，也是通常它令我们头疼的点。

逻辑

很经典的， $\max(a,b)\le c\iff a\le c\wedge b\le c,\max(a,b)\ge c\iff a\ge c\vee b\ge c$ 。

通常更有用的是第一个，因为复杂问题下，给出的诸多“限制”自带逻辑与的含义， $a\le c\wedge b\le c$ 虽然增加了条件的个数，但是却化简了条件。

当然，后者也很有用，因为当 $a,b,c$ 都是一坨式子的时候，将其变为可以移项的不等式实在是很有用的一件事。

下面给出一个例子，这在 Exchange Arguments 问题及其变种中十分有用：

$\begin{aligned}& \max(f_x,f_{y}-g_x)< \max(f_y,f_x-g_y)\\&\iff\left( f_x< \max(f_y,f_x-g_y)\right)\wedge\left( f_y-g_x< \max(f_y,f_x-g_y)\right)\\&\iff \left((f_x<f_y)\vee (f_x< f_x-g_y)\right)\wedge \left((f_y-g_x<f_y)\vee (f_y-g_x< f_x-g_y)\right)\\&\iff\left((f_x<f_y)\vee (g_y<0)\right)\wedge \left((g_x>0)\vee (f_x+g_x>f_y+g_y)\right)\end{aligned}$

不去深究具体含义，这确实为我们带来了很直观的等价版本。

同样的方式也可以用来处理集合的交并，不过直接对交并统计的题目较为冷门，此处不展开。

绝对值

绝对值与 $\max$ 的互转同样很常用。

很经典的， $|a-b|=\max(a-b,b-a)$ ，这在曼哈顿距离中十分常用（简单例题：[AGC034D] Manhattan Max Matching），例如如果我们要求距离每个点的最大曼哈顿距离，由于求最大值，所以 $\max$ 的结合律可以让我们拆掉内层的 $\max$ ，于是我们可以用 $2^k n$ （ $k$ 是维数）的复杂度求解。

例题：[ARC107F] Sum of Abs。

本题就把 $\max |\sum b|$ 拆成了"所有 $b$ 的符号必须相同即可贡献到答案"，然后再用一些网络流技巧来限制符号相同。

还有一个容易忽视的转化： $\max(a,b)=\frac{a+b+|a-b|}{2}$ ，如果我们把加和乘看作“没有代价”的话，那么这个式子实现了 $\max(a,b)$ 和 $|a-b|$ 的直接转化，若 $a-b$ 能化简那再好不过。

例题：CF2062F。

给定序列 $a,b$ ，一个完全图， $w(i,j)=\max(a_i+b_j,a_j+b_i)$ ，对每个 $k$ 求 $k$ 条边的最短哈密顿路。

$n\le 3000$ 。

$\max(a_i+b_j,a_j+b_i)=\frac{a_i+b_i+a_j+b_j+|a_i+b_j-a_j-b_i|}{2}$

忽略掉除以 $2$ ，对一条路径，前面的贡献就是 $2(\sum a+\sum b)- (a+b)_{first,last}$ ，后面的贡献就是将位置视作 $x_i=(a_i-b_i)$ ，不断移动的路程。

显然，固定 $first,last$ ，后面的贡献最小是 $2(\max x-\min x)-|x_{first}-x_{last}|$ 。

到这里已经可以 $\rm dp$ 了，按照 $x$ 排序后，设 $f_{i,j,0/1/2}$ 表示前 $i$ 个，选了 $j$ 个，无 $first,last$ /有其一/都有， $\min x$ 的贡献在 $j$ 由 $0$ 变为 $1$ 时算， $\max$ 的贡献可以统计答案时算。